Skip to content

3104. Find Longest Self-Contained Substring

  • Time: $O(26n) = O(n)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
 public:
  int maxSubstringLength(string s) {
    int ans = -1;
    vector<int> 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:
  // Similar to 395. Longest Substring with At Least K Repeating Characters
  int maxSubstringLengthWithNUniqueLetters(const string& s, int n,
                                           const vector<int>& allCount) {
    int res = -1;
    // the number of unique letters
    int uniqueLetters = 0;
    // the number of letters that have all their frequency in the substring
    int lettersHavingAllFreq = 0;
    vector<int> 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;
      }
      // Since both the number of unique letters and the number of letters
      // having all their frequency are equal to n, this is a valid window.
      // Implcit: uniqueLetters == n
      if (lettersHavingAllFreq == n && r - l + 1 < s.length())
        res = max(res, r - l + 1);
    }

    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public int maxSubstringLength(String s) {
    int ans = -1;
    int count[] = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

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

    return ans;
  }

  // Similar to 395. Longest Substring with At Least K Repeating Characters
  private int maxSubstringLengthWithNUniqueLetters(final String s, int n, int[] allCount) {
    int res = -1;
    // the number of unique letters
    int uniqueLetters = 0;
    // the number of letters that have all their frequency in the substring
    int lettersHavingAllFreq = 0;
    int[] count = new int[26];

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (++count[s.charAt(r) - 'a'] == 1)
        ++uniqueLetters;
      if (count[s.charAt(r) - 'a'] == allCount[s.charAt(r) - 'a'])
        ++lettersHavingAllFreq;
      while (uniqueLetters > n) {
        if (count[s.charAt(l) - 'a'] == allCount[s.charAt(l) - 'a'])
          --lettersHavingAllFreq;
        if (--count[s.charAt(l) - 'a'] == 0)
          --uniqueLetters;
        ++l;
      }
      // Since both the number of unique letters and the number of letters
      // having all their frequency are equal to n, this is a valid window.
      // Implcit: uniqueLetters == n
      if (lettersHavingAllFreq == n && r - l + 1 < s.length())
        res = Math.max(res, r - l + 1);
    }

    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def maxSubstringLength(self, s: str) -> int:
    allCount = collections.Counter(s)

    # Similar to 395. Longest Substring with At Least K Repeating Characters
    def maxSubstringLengthWithNUniqueLetters(n: int) -> int:
      res = -1
      # the number of unique letters
      uniqueLetters = 0
      # the number of letters that have all their frequency in the substring
      lettersHavingAllFreq = 0
      count = collections.Counter()

      l = 0
      for r, c in enumerate(s):
        count[c] += 1
        if count[c] == 1:
          uniqueLetters += 1
        if count[c] == allCount[c]:
          lettersHavingAllFreq += 1
        while uniqueLetters > n:
          if count[s[l]] == allCount[s[l]]:
            lettersHavingAllFreq -= 1
          count[s[l]] -= 1
          if count[s[l]] == 0:
            uniqueLetters -= 1
          l += 1
        # Since both the number of unique letters and the number of letters
        # having all their frequency are equal to n, this is a valid window.
        # Implcit: uniqueLetters == n
        if lettersHavingAllFreq == n and r - l + 1 < len(s):
          res = max(res, r - l + 1)

      return res

    return max(maxSubstringLengthWithNUniqueLetters(n)
               for n in range(1, 27))