Share my DP solution with constant space


  • 0
    J
    public int lengthOfLongestSubstringTwoDistinct(String s) {
    	if (s == null) return 0;
    	if (s.length() < 3) return s.length();
    
    	int maxLen = 2;
    	int maxLenTail = 2;
    	int tailRepeat = 1;
    
    	char maxch1 = s.charAt(0), maxch2 = s.charAt(1);
    	if (maxch1 == maxch2) tailRepeat = 2;
    
    	for (int i = 2; i < s.length(); i++) {
    		char ch = s.charAt(i);
    		if (ch == maxch2 || ch == maxch1 || maxch1 == maxch2) {
    			maxLenTail++;
    			maxLen = Math.max(maxLen, maxLenTail);
    
    		    if (ch != maxch2) {
    		        maxch1 = maxch2;
    		        maxch2 = ch;
    		        tailRepeat = 1;
    		    } else {
    		    	tailRepeat++;
    		    }
    		} else {
    			maxLenTail = tailRepeat + 1;
    			tailRepeat = 1;
    			maxch1 = maxch2;
    			maxch2 = ch;
    			maxLen = Math.max(maxLen, maxLenTail);
    		}
    	}
    	return maxLen;
    }

  • 0
    K

    I don't quite get how this is DP. What was the recursive solution you used as a basis for the DP solution?


Log in to reply
 

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