My java DP O(n) solution without using HashSet


  • 0
    G

    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.
                cur++;
                if(cur > max){max = cur;}
            }
            else{
                int index = positions[s.charAt(endIn)] - 1;
                while(startFrom <= index){
                    positions[s.charAt(startFrom)] = 0;
                    startFrom++;
                }
                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.