Question Description

Screen Shot 2016-10-07 at 20.00.12.png

My Code

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() < 1) return 0;
        int[] calculate = new int[s.length()];
        Arrays.fill(calculate, -1);
        for (int i = 0; i < s.length(); i++) {
            dp(s, calculate, i);
        }
        int result = 0;
        for (int i: calculate
                ) {
            if (i > result) result = i;
        }
        return result;
    }
    
    private int dp(String s, int[] calculate, int i) {
        if (i == 0) {
            calculate[i] = 1;
            return 1;
        }
        if (calculate[i] != -1) return calculate[i];
        String sub = s.substring(i - dp(s, calculate, i - 1), i);
        String thisChar = String.valueOf(s.charAt(i));
        calculate[i] = sub.contains(thisChar) ? sub.length() - sub.indexOf(thisChar) : calculate[i - 1] + 1;
        return calculate[i];
    }
}

Test Result

Screen Shot 2016-10-07 at 19.59.42.png

Solution

Dynamic programming. Use int[] calculate to record the max length of String ended index i. The value of calculate[i] relies on calculate[i - 1]. If max-length String that ends with index i - 1 doesn't contain char at i, calculate[i] = 1 + calculate[i - 1]. Else, calculate[i] = 1 + (length of String begins after char at i in max-length String that ends with index i - 1).