Practice/Amazon/Leetcode 3104. Find Longest Self-Contained Substring

Leetcode 3104. Find Longest Self-Contained Substring

CodingMust

Problem

Given a string s, find the length of the longest self-contained substring. A substring is considered self-contained if every character that appears in the substring has all of its occurrences within that substring's boundaries. In other words, no character in the substring appears anywhere outside of it in the original string.

For example, in the string "abcda", the substring "bcd" (from index 1 to 3) is self-contained because characters 'b', 'c', and 'd' only appear within this range and nowhere else in the string.

Requirements

1. Return the length of the longest self-contained substring
2. If multiple substrings of the same maximum length exist, return that length
3. A single character is always self-contained if it appears only once
4. The entire string is self-contained if all characters' occurrences are within the string itself

Constraints

• 1 ≤ length of s ≤ 105
• s consists of lowercase English letters only
• Time complexity should be O(n) or O(n²) where n is the length of the string
• Space complexity should be O(1) or O(26) for character frequency tracking

Examples

Example 1:

Input: s = "abcda" Output: 3 Explanation: The substring "bcd" (indices 1-3) is self-contained. Characters 'b', 'c', 'd' only appear within this range.

Example 2:

Input: s = "abcdef" Output: 6 Explanation: Each character appears exactly once, so the entire string is self-contained.

Example 3:

Input: s = "aabbaa" Output: 6 Explanation: The entire string is self-contained since 'a' and 'b' both appear throughout specific ranges that encompass the whole string.

Example 4:

Input: s = "abacabad" Output: 8 Explanation: Character 'a' appears at indices 0, 2, 4, 6, so any valid substring containing any character must include all positions where 'a' appears, resulting in the entire string.