For example, Given s =
“eceba”
,
T is "ece" which its length is 3.
public class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { // Adopt sliding window // start --- the starting position of the window // i --- the first distinct character after the window // This algorithm is easy for understanding but need additional extra memory. int start = 0; int cnt = 0; // Number of distinct characters int[] charSet = new int[256]; int maxLen = 0; for (int i = 0; i < s.length(); i++) { if (charSet[s.charAt(i)] == 0) cnt++; charSet[s.charAt(i)]++; while (cnt > 2) { // If the number of distinct characters is more than 2, // move start until a distinct character disapear. charSet[s.charAt(start)]--; if (charSet[s.charAt(start)] == 0) cnt--; start++; } maxLen = Math.max(i - start + 1, maxLen); } return maxLen; } }
No comments:
Post a Comment