Find Longest Self-Contained Substring

Find Longest Self-Contained Substring

What is this problem about?

The Find Longest Self-Contained Substring coding problem asks you to find the longest substring such that every character present in that substring appears only within that substring in the entire string. Additionally, the substring must be shorter than the whole string. If no such substring exists, return 0 (or -1).

Why is this asked in interviews?

Amazon use this "Hard" problem to test a candidate's ability to analyze global constraints within local windows. It requires a sophisticated understanding of String and Interval interview patterns. You need to know the first and last occurrences of every character to determine the "minimum boundaries" of a valid segment. It evaluations your ability to use Greedy expansion and range merging.

Algorithmic pattern used

This problem involves Interval Precomputation and Expansion.

1. Precompute the first[c] and last[c] index for every character 'a'-'z'.
2. For every character c, consider the range [first[c], last[c]] as a potential starting point.
3. Expand this range: if any other character d is found within the range, the range must expand to include last[d] and potentially first[d].
4. If the range expands beyond its original boundaries, continue checking all characters inside the new range until it stabilizes.
5. If the final stabilized range [L, R] contains only characters whose entire occurrences are within [L, R], it is a "self-contained" candidate.
6. The result is the max length of such a valid candidate that is not the entire string.

Example explanation

String: "abacaba"

1. 'a' range: [0, 6]. Stabilizes to [0, 6]. (Full string, ignore).
2. 'b' range: [1, 5]. Inside are 'a', 'c'. Expanding to include 'a' makes it [0, 6].
3. 'c' range: [3, 3]. Stabilizes to [3, 3]. Length = 1. If the string was "abcde", any single character would be length 1.

Common mistakes candidates make

• Naive Search: Trying all $O(n^2)$ substrings, which is too slow.
• Incomplete Expansion: Not re-checking characters after an expansion, leading to a window that still contains "external" occurrences.
• Empty/Invalid Result: Forgetting the condition that the substring must be strictly smaller than the original string.

Interview preparation tip

Think of characters as intervals. A self-contained substring is a union of character intervals that doesn't intersect with the parts of any included interval that lie outside. This is a common pattern in compiler design and string compression algorithms.