My java DP 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 1 plus maxLength at i; If the HashSet contain 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 int lengthOfLongestSubstring(String s) {
    
        if(s == null || s.length() == 0){return 0;}
        int[] positions = new int[128];
        int j = 0;
        int max = 0;
        int cur = 0;
        for(int i = 0; i < s.length(); i++){
            if(positions[s.charAt(i)] == 0){
                positions[s.charAt(i)] = i + 1; // we add 1 so that it would not conflict with index 0.
                cur++;
                if(cur > max){max = cur;}
            }
            else{
                int index = positions[s.charAt(i)] - 1;
                while(j <= index){
                    positions[s.charAt(j)] = 0;
                    j++;
                }
                cur = i - j + 1;
                positions[s.charAt(i)] = i + 1;
            }
        }
        return max;
        
    }
    

    }


Log in to reply
 

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