Find Longest Self-Contained Substring in C++

Problem Description

So, you think you can just waltz into a string and find the longest self-contained substring? Well, think again! The problem is to find the longest substring that contains exactly n unique characters. Imagine you’re at a party, and you can only invite a certain number of friends (unique characters) to your exclusive VIP section. If you invite more than that, you’ll have to kick some out!

In simpler terms, given a string, you need to find the longest substring that contains exactly n unique characters. If you’re thinking, “How hard can that be?” just remember the last time you tried to manage a group of friends at a restaurant. Too many choices, and someone always ends up sitting alone!

Code Solution


class Solution {
 public:
  int maxSubstringLength(string s) {
    int ans = -1;
    vector count(26);

    for (const char c : s)
      ++count[c - 'a'];

    for (int n = 1; n <= 26; ++n)
      ans = max(ans, maxSubstringLengthWithNUniqueLetters(s, n, count));

    return ans;
  }

 private:
  int maxSubstringLengthWithNUniqueLetters(const string& s, int n,
                                           const vector& allCount) {
    int res = -1;
    int uniqueLetters = 0;
    int lettersHavingAllFreq = 0;
    vector count(26);

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (++count[s[r] - 'a'] == 1)
        ++uniqueLetters;
      if (count[s[r] - 'a'] == allCount[s[r] - 'a'])
        ++lettersHavingAllFreq;
      while (uniqueLetters > n) {
        if (count[s[l] - 'a'] == allCount[s[l] - 'a'])
          --lettersHavingAllFreq;
        if (--count[s[l] - 'a'] == 0)
          --uniqueLetters;
        ++l;
      }
      if (lettersHavingAllFreq == n && r - l + 1 < s.length())
        res = max(res, r - l + 1);
    }

    return res;
  }
};

Approach Explanation

The code uses a sliding window technique to maintain a substring that contains exactly n unique characters. It keeps track of the count of each character and adjusts the window size dynamically. If the number of unique characters exceeds n, it shrinks the window from the left until it meets the requirement again. This way, it efficiently finds the longest valid substring.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the length of the string.
Space Complexity	O(1) for the count array since it only stores counts for 26 characters.

Real-World Example

Imagine you’re at a buffet with a limited number of dishes (unique characters). You can only try a certain number of dishes at a time (n unique characters). If you try to grab more than that, you’ll have to put some back! The longest line you can form with your plate while adhering to this rule is akin to finding the longest self-contained substring.