3. Longest Substring Without Repeating Characters

Description

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int[] dp = new int[s.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            int realIndex = i - 1;
            int index = s.substring(realIndex - dp[i - 1], realIndex).lastIndexOf(s.charAt(realIndex));
            if (index == -1) dp[i] = dp[i - 1] + 1;
            else dp[i] = dp[i - 1] - index;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}