Longest Substring with At Most K Distinct Characters

Problem Statement

You are given a string s and an integer k. Your task is to find the length of the longest substring in s that contains at most k distinct characters.

Examples

Example 1

Input: s = “eceba", K = 2

Output: 3

Explanation:

The longest substring with at most 2 distinct characters is "ece".

Different Approaches

1 Brute Force Approach

Algorithm:

1. Initialize maxLen to 0.
2. Iterate i from 0 to n - 1, where n is the length of the string s.
   1. Iterate j from i to n - 1.
      1. Consider the substring s[i...j].
      2. Count the number of distinct characters in the substring by inserting in set.
      3. If the count of distinct characters is less than or equal to k, update maxLen with the maximum length of the substring.
3. Return maxLen.

Code Implementation in C++:

#include <iostream>
#include <unordered_set>

using namespace std;

int longestSubstringWithAtMostKDistinctChars(string s, int k) {
    int n = s.size();
    int maxLen = 0;

    // Iterate through all possible substrings
    for (int i = 0; i < n; i++) {
        unordered_set<char> uniqueChars;
        for (int j = i; j < n; j++) {
            uniqueChars.insert(s[j]);
            if (uniqueChars.size() <= k) {
                maxLen = max(maxLen, j - i + 1);
            }
        }
    }

    // Return the maximum length of the substring
    return maxLen;
}

int main() {
    string s1 = "eceba";
    int k1 = 2;
    cout << "Longest substring with at most " << k1 << " distinct characters in \"" << s1 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s1, k1) << endl;

    string s2 = "aa";
    int k2 = 1;
    cout << "Longest substring with at most " << k2 << " distinct characters in \"" << s2 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s2, k2) << endl;

    return 0;
}

OR with map

#include <iostream>
#include <unordered_map>

using namespace std;

int longestSubstringWithAtMostKDistinctChars(string s, int k) {
    int n = s.size();
    int maxLen = 0;

    // Iterate through all possible substrings
    for (int i = 0; i < n; i++) {
        unordered_map<char, int> mp; // Hashmap to store the frequency of characters in the substring
        for (int j = i; j < n; j++) {
            mp[s[j]]++; // Increase the frequency of the current character
            if (mp.size() <= k) { // If the count of distinct characters is less than or equal to k
                maxLen = max(maxLen, j - i + 1); // Update maxLen with the maximum length of the substring
            }
        }
    }

    // Return the maximum length of the substring
    return maxLen;
}

int main() {
    string s1 = "eceba";
    int k1 = 2;
    cout << "Longest substring with at most " << k1 << " distinct characters in \"" << s1 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s1, k1) << endl;

    string s2 = "aa";
    int k2 = 1;
    cout << "Longest substring with at most " << k2 << " distinct characters in \"" << s2 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s2, k2) << endl;

    return 0;
}

Complexity Analysis:

Time Complexity:O(n^2)

Space Complexity:O(1)

2 Sliding Window with Map

Algorithm:

1. Initialize two pointers left and right to 0.
2. Initialize a hashmap mp to store the frequency of characters in the window.
3. Initialize a variable maxLen to 0.
4. Iterate through the string:
   1. Update the frequency of the current character in mp.
   2. If the number of distinct characters in the current window exceeds k, move the left pointer to minimize the window.
   3. Update maxLen with the maximum length of the window.
5. Return maxLen.

Example:

Consider the string s = “eceba” and k = 2

Initialization:

• left = 0, right = 0
• maxLen = 0
• mp = {} (empty hashmap)
• distinctChars = 0

s = "eceba"
k = 2
left = 0, right = 0
maxLen = 0
mp = {}
distinctChars = 0

Iteration 1:

• Consider character e.
• Increment the frequency of e in mp.
• Since mp['e'] == 1, increment distinctChars.
• Update maxLen to max(0, 0 - 0 + 1) = 1.

s = "eceba"
k = 2
left = 0, right = 0
maxLen = 1
mp = {'e': 1}
distinctChars = 1

Iteration 2:

• Consider character c.
• Increment the frequency of c in mp.
• Since mp['c'] == 1, increment distinctChars.
• Update maxLen to max(1, 1 - 0 + 1) = 2.

s = "eceba"
k = 2
left = 0, right = 1
maxLen = 2
mp = {'e': 1, 'c': 1}
distinctChars = 2

Iteration 3:

• Consider character e.
• Increment the frequency of e in mp.
• Update maxLen to max(2, 2 - 0 + 1) = 3.

s = "eceba"
k = 2
left = 0, right = 2
maxLen = 3
mp = {'e': 2, 'c': 1}
distinctChars = 2

Iteration 4:

• Consider character b.
• Increment the frequency of b in mp.
• Since distinctChars > k, move the left pointer to minimize the window.
• Decrease the frequency of e in mp.
• Since mp['e'] > 0, decrement distinctChars.

s = "eceba"
k = 2
left = 1, right = 3
maxLen = 3
mp = {'e': 1, 'c': 1, 'b': 1}
distinctChars = 2

Iteration 5:

• Consider character a.
• Increment the frequency of a in mp.
• Since distinctChars > k, move the left pointer to minimize the window.
• Decrease the frequency of c in mp.
• Since mp['c'] > 0, decrement distinctChars.

s = "eceba"
k = 2
left = 2, right = 4
maxLen = 3
mp = {'e': 1, 'c': 0, 'b': 1, 'a': 1}
distinctChars = 2

Final Result:

The longest substring with at most 2 distinct characters is "ece", with a length of 3.

Code Implementation in C++:

#include <iostream>
#include <unordered_map>

using namespace std;

int longestSubstringWithAtMostKDistinctChars(string s, int k) {
    unordered_map<char, int> mp;
    int n = s.size();
    int maxLen = 0;
    int distinctChars = 0;

    int left = 0, right = 0;

    // Sliding window approach
    while (right < n) {
        // Increase the frequency of the current character
        mp[s[right]]++;

        // If the frequency becomes 1, increment the count of distinct characters
        if (mp[s[right]] == 1) {
            distinctChars++;
        }

        // If the number of distinct characters exceeds k, move the left pointer
        while (distinctChars > k) {
            // Decrease the frequency of the leftmost character
            mp[s[left]]--;

            // If the frequency becomes 0, decrement the count of distinct characters
            if (mp[s[left]] == 0) {
                distinctChars--;
            }

            // Move the left pointer to minimize the window
            left++;
        }

        // Update maxLen with the maximum length of the window
        maxLen = max(maxLen, right - left + 1);

        // Move the right pointer to expand the window
        right++;
    }

    // Return the maximum length of the window
    return maxLen;
}

int main() {
    string s1 = "eceba";
    int k1 = 2;
    cout << "Longest substring with at most " << k1 << " distinct characters in \"" << s1 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s1, k1) << endl;

    string s2 = "aa";
    int k2 = 1;
    cout << "Longest substring with at most " << k2 << " distinct characters in \"" << s2 << "\": ";
    cout << longestSubstringWithAtMostKDistinctChars(s2, k2) << endl;

    return 0;
}

OR

    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> cnt;
        int n = s.size();
        int ans = 0, j = 0;
        for (int i = 0; i < n; ++i) {
            cnt[s[i]]++;
            while (cnt.size() > k) {
                if (--cnt[s[j]] == 0) {
                    cnt.erase(s[j]);
                }
                ++j;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }

Complexity Analysis:

Time Complexity: O(n)

• The time complexity of the sliding window approach is O(N), where N is the length of the input string s.
• In each iteration, both the left and right pointers move at most N steps, and the frequency of characters is updated in constant time.

Space Complexity:O(k)

• The space complexity is O(k), where k is the number of distinct characters allowed in the window.
• The space required for the hashmap mp is proportional to the number of distinct characters.