My java DP O(n) solution without using HashSet

  • 0

    public class Solution {

    // the max length subArray must be ending in some position i of String s, so we can use a DP to solve this problem. We calculate the maxLength of the subString that ends in each position i can have, and keep a HashSet to store the characters of the subString. If the HashSet does not contain the s.charAt(i+1), then the maxLength that ends in i + 1 is maxLength at i plus 1; If the HashSet contains the s.charAt(i+1), then we need to delete all the characters before positions[s.charAt(i+1)] of string s.

    // we define a positions[] to keep all the indexs of current substring that ends in i. In addition, positions[] also act as the HashSet of current substring.

    public class Solution {

    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){return 0;}
        int[] positions = new int[128];
        int startFrom = 0;
        int max = 0;
        int cur = 0;
        for(int endIn = 0; endIn < s.length(); endIn++){
            if(positions[s.charAt(endIn)] == 0){
                positions[s.charAt(endIn)] = endIn + 1;
                // we add 1 so that character whose position is 0 would not conflict with character not in the HashSet.
                if(cur > max){max = cur;}
                int index = positions[s.charAt(endIn)] - 1;
                while(startFrom <= index){
                    positions[s.charAt(startFrom)] = 0;
                cur = endIn - startFrom + 1;
                positions[s.charAt(endIn)] = endIn + 1;
        return max;


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.