Find Longest Self-Contained Substring - Solution & Explanation
Problem Statement
Given a string s, your task is to find the length of the longest self-contained substring of s.
A substring t of a string s is called self-contained if t != s and for every character in t, it doesn't exist in the rest of s.
Return the length of the longest self-contained substring of s if it exists, otherwise, return -1.
Example 1:
Input: s = "abba"
Output: 2
Explanation:
Let's check the substring "bb". You can see that no other "b" is outside of this substring. Hence the answer is 2.
Example 2:
Input: s = "abab"
Output: -1
Explanation:
Every substring we choose does not satisfy the described property (there is some character which is inside and outside of that substring). So the answer would be -1.
Example 3:
Input: s = "abacd"
Output: 4
Explanation:
Let's check the substring "abac". There is only one character outside of this substring and that is "d". There is no "d" inside the chosen substring, so it satisfies the condition and the answer is 4.
Constraints:
2 <= s.length <= 5 * 104sconsists only of lowercase English letters.
Approach Overview
Problem Overview: Given a string, find the longest substring where every character inside the substring does not appear outside it. In other words, for each character included, all of its occurrences in the original string must lie completely inside the chosen substring.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Generate every possible substring using two nested loops and validate whether it is self-contained. For each substring s[i..j], scan the entire string and verify that any character appearing inside the substring does not appear outside its boundaries. This requires repeated scanning and membership checks, which leads to cubic complexity. While inefficient, this approach clarifies the exact constraint: every character inside the window must have all its occurrences within that window.
Approach 2: Enumeration with Character Boundary Tracking (O(n^2) time, O(26) space)
Precompute the first and last occurrence of each character using a hash table or fixed array. When enumerating substrings starting at index i, expand the right boundary j while tracking the minimum first occurrence and maximum last occurrence for characters seen so far. A substring is self-contained if every character's first occurrence is >= i and last occurrence is <= j. This avoids scanning the entire string for validation and reduces the complexity to quadratic. In practice, the alphabet is small, so tracking boundaries is cheap.
Approach 3: Enumeration with Prefix Frequency + Binary Search (O(n^2 log n) time, O(n) space)
Build prefix frequency arrays for each character using the prefix sum technique. This lets you query the frequency of any character inside a substring in O(1). For a chosen start index, you can use binary search to find the farthest valid end position while ensuring that every character present in the substring has zero occurrences outside it. Prefix queries quickly verify counts inside and outside the candidate window. This approach is useful when validation conditions are complex or when substring frequency queries must be repeated many times.
Recommended for interviews: Enumeration with character boundary tracking is the practical solution. Brute force demonstrates understanding of the definition of a self-contained substring, but interviewers usually expect you to reduce redundant scans using precomputed first/last indices. That optimization keeps the logic simple while improving performance significantly.
Solution
We notice that the start of a substring that meets the conditions must be the position where a character appears for the first time.
Therefore, we can use two arrays or hash tables first and last to record the positions where each character appears for the first time and the last time, respectively.
Next, we enumerate each character c. Suppose the position where c first appears is i, and the position where it last appears is mx. Then we can start traversing from i. For each position j, we find the position a where s[j] first appears and the position b where it last appears. If a < i, it means that s[j] is on the left of c, which does not meet the enumeration conditions, and we can exit the loop directly. Otherwise, we update mx = max(mx, b). If mx = j and j - i + 1 < n, we update the answer to ans = max(ans, j - i + 1).
Finally, return the answer.
The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|). Where n is the length of the string s; and |\Sigma| is the size of the character set. In this problem, the character set is lowercase letters, so |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | For conceptual understanding or very small strings |
| Enumeration with First/Last Occurrence Tracking | O(n^2) | O(26) | General solution; efficient when alphabet size is small |
| Prefix Frequency + Binary Search | O(n^2 log n) | O(n) | Useful when many substring frequency queries are needed |
Video Solution
3104. Find Longest Self-Contained Substring (Leetcode Hard) • Programming Live with Larry • 1,064 views views
Frequently Asked Questions
Is Find Longest Self-Contained Substring easy or hard?
Find Longest Self-Contained Substring Python/Java solution
How to solve Find Longest Self-Contained Substring in O(n)?
What is the best approach for Find Longest Self-Contained Substring?
Is Find Longest Self-Contained Substring asked at Google/Amazon/Meta?
What data structure is used in Find Longest Self-Contained Substring?
What is the time complexity of Find Longest Self-Contained Substring?
Ready to solve this problem?
Practice Find Longest Self-Contained Substring with our built-in code editor and test cases.
Practice on FleetCode