Find Longest Self-Contained Substring Solution in Python

Problem Description

So, you think you can find the longest self-contained substring? Well, welcome to the club! The problem is simple yet complex, like trying to find your keys in a messy room. You are given a string, and your task is to find the longest substring that contains all unique characters. Imagine you’re at a party, and you want to hang out with friends who are not already in a group. You want to maximize your social circle without repeating any friends.

In technical terms, the problem is defined as follows: Given a string s, find the length of the longest substring that contains at most k unique characters.

Code Solution


class Solution:
    def maxSubstringLength(self, s: str) -> int:
        allCount = collections.Counter(s)

        def maxSubstringLengthWithNUniqueLetters(n: int) -> int:
            res = -1
            uniqueLetters = 0
            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
                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))

Approach Explanation

The code uses a sliding window technique to maintain a substring that contains at most n unique characters. It counts the frequency of characters in the current window and adjusts the left pointer of the window when the number of unique characters exceeds n. The result is updated whenever a valid window is found.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * 26) = O(n)
Space Complexity	O(1)

Real-World Example

Imagine you are at a buffet with a variety of dishes. You want to fill your plate with different items without repeating any. The longest self-contained substring is like your plate filled with unique dishes. If you keep adding the same dish, you’ll have to remove something else to make space. The goal is to maximize the variety on your plate!