Leetcode 3090: Maximum Length Substring with two occurences

In this exercise, we want to find the maximum substring that has at most 2 of any character.

Maximum substring problems

I am going to give you a secret tip just between us. When you see a maximum substring problem you should immediately think: “2-pointers”! You can thank me later.

Algorithm

We will just count the occurences of each character in an array. Whenever we encounter a character that is already 2-times in the substring, we reduce the substring using the left pointer until we can keep going.

2-pointer algorithm

We retain the maximum length max while we go though the algorithm.

Code

public int maximumLengthSubstring(String s) {
    // two pointers
    int n = s.length();
    int[] count = new int[256];
    // The 2 pointers start and end 
    // pointing to the start and end of the substring
    int start = 0;
    int end = 0;
    int max = 0;
    while(end < n) {
        char nextChar = s.charAt(end);
        if (count[nextChar] == 2) {
            max = Math.max(max, end - start);
            count[s.charAt(start++)]--;
        } else {
            count[nextChar]++;
            end++;
        }
    }
    max = Math.max(max, end - start);
    return max;
}

Time and Space complexity

Time complexity is O(n) and space complexity is O(1), since the array count is of fixed length, and start, end and max are simple integers.

Need more help?

Contact me for interview prep and coaching: poitevinpm@gmail.com