Find Longest Self-Contained Substring Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the classic quest for the longest self-contained substring! Imagine you’re at a party, and you want to find the longest group of friends who all have unique names. You know, no duplicates allowed! The problem is, you have a string of characters (like names) and you need to find the longest substring where each character appears at least once, but not more than the number of unique characters you want to allow.

In simpler terms, you want to find the longest stretch of characters in a string where you can have a specific number of unique characters. If you think about it, it’s like trying to fit all your friends into a car without exceeding the seating limit.

Code Solution


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;
  }

  private int maxSubstringLengthWithNUniqueLetters(final String s, int n, int[] allCount) {
    int res = -1;
    int uniqueLetters = 0;
    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;
      }
      if (lettersHavingAllFreq == n && r - l + 1 < s.length())
        res = Math.max(res, r - l + 1);
    }

    return res;
  }
}

Approach

The approach taken in this solution is a two-pointer technique combined with a frequency count. The outer loop iterates through the number of unique letters allowed, while the inner loop expands and contracts a sliding window to find the longest substring that meets the criteria. The key is to maintain counts of unique letters and ensure that the substring contains the required number of unique characters.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the length of the string.
Space Complexity	O(1), since the space used for the count array is constant (26 letters).

Real-World Example

Imagine you’re at a buffet with a variety of dishes. You want to fill your plate with the longest combination of unique dishes without repeating any. If you can only choose 3 different types of dishes, you’ll be looking for the longest stretch of unique dishes that fit that criteria. This is exactly what the algorithm does with characters in a string!