Is Find Longest Self-Contained Substring easy or hard?

LeetCode classifies this problem as Hard because the definition of a self-contained substring is subtle and brute force solutions are inefficient. Solving it effectively requires reasoning about character occurrence ranges and optimizing substring validation.

Find Longest Self-Contained Substring Python/Java solution

Typical solutions enumerate substring boundaries and track character ranges using arrays or hash maps. The logic is language-agnostic and can be implemented in Python, Java, C++, Go, or TypeScript with similar O(n^2) complexity.

How to solve Find Longest Self-Contained Substring in O(n)?

A strict O(n) solution is difficult because many candidate substrings must be validated. Most accepted solutions enumerate start positions and extend the right boundary while checking character ranges, giving O(n^2) time. Precomputing first and last occurrences or prefix frequencies keeps validation constant time.

What is the best approach for Find Longest Self-Contained Substring?

The most practical approach enumerates substrings while tracking the first and last occurrence of each character. If every character seen in the current window has its first occurrence >= left boundary and last occurrence <= right boundary, the substring is self-contained. This reduces repeated scans and runs in O(n^2) time with O(26) extra space.

Is Find Longest Self-Contained Substring asked at Google/Amazon/Meta?

Problems involving substring constraints, character frequency tracking, and interval validation frequently appear in interviews at companies like Google, Amazon, and Meta. This question tests string processing, boundary tracking, and optimization from brute force to efficient enumeration.

What data structure is used in Find Longest Self-Contained Substring?

Common structures include hash tables or fixed arrays to store first and last character occurrences. Prefix sum arrays can also be used to query character frequencies inside substrings in O(1). These structures help validate whether characters appear outside the candidate substring.

What is the time complexity of Find Longest Self-Contained Substring?

The optimized enumeration approach runs in O(n^2) time because each starting index expands the substring once while updating character boundaries. Space complexity is O(26) for storing first and last occurrences of characters. A naive brute-force validation approach can reach O(n^3).

Description Hints 5 Solution Video 34:15

3104. Find Longest Self-Contained Substring

Q: Is Find Longest Self-Contained Substring asked at Google/Amazon/Meta?

Problems involving substring constraints, character frequency tracking, and interval validation frequently appear in interviews at companies like Google, Amazon, and Meta. This question tests string processing, boundary tracking, and optimization from brute force to efficient enumeration.

Q: What data structure is used in Find Longest Self-Contained Substring?

Common structures include hash tables or fixed arrays to store first and last character occurrences. Prefix sum arrays can also be used to query character frequencies inside substrings in O(1). These structures help validate whether characters appear outside the candidate substring.

Q: What is the time complexity of Find Longest Self-Contained Substring?

The optimized enumeration approach runs in O(n^2) time because each starting index expands the substring once while updating character boundaries. Space complexity is O(26) for storing first and last occurrences of characters. A naive brute-force validation approach can reach O(n^3).

Hard58.6% acceptance1 companyPremium elsewhere, free here

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 * 10⁴
s consists only of lowercase English letters.

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Fix the start index of the substring.

Hint 2

For some fixed index start, let's try to find some index end such that this substring satisfies the property and also end is as maximum as possible.

Hint 3

Write some recursive function shrink(start, end) that gives a substring. If the substring is valid, then return end. Otherwise, it reduces <end to reach some valid end.

Hint 4

For some shrink(start, end), if the substring is not valid, it means there is some character that is both inside and outside of the substring. Now try to reduce end such that it does not contain that character anymore.

Hint 5

If you implement the shrink(start, end) function optimally, you'll achieve O(n * 26 * 26) by using partial sum.

34:15

Still stuck?Read the written solution, or watch a walkthrough.

Open solution