Solution Approach

First, we create two hash tables (or dictionaries) first and last to record the first and last occurrence positions of each character in the string:

first, last = {}, {} for i, c in enumerate(s):  if c not in first:  first[c] = i  last[c] = i

Next, we enumerate each character c as a potential starting point for our self-contained substring. We only consider positions where characters appear for the first time (stored in first):

for c, i in first.items():  mx = last[c] # Initialize mx with the last occurrence of character c

Here, i is the starting position of our potential substring, and mx tracks the rightmost position we must reach to include all occurrences of characters we've encountered.

For each starting position i, we traverse from position i to the end of the string:

for j in range(i, n):  a, b = first[s[j]], last[s[j]]

At each position j, we get:

• a: the first occurrence position of character s[j]
• b: the last occurrence position of character s[j]

If a < i, it means character s[j] has already appeared before our starting position i. This violates the self-contained property, so we break out of the inner loop:

if a < i:  break

Otherwise, we update mx to ensure we include all occurrences of s[j]:

mx = max(mx, b)

If mx == j, it means we've reached a position where we've included all necessary occurrences of all characters seen so far. If additionally j - i + 1 < n (ensuring the substring is not the entire string), we have found a valid self-contained substring:

if mx == j and j - i + 1 < n:  ans = max(ans, j - i + 1)

The algorithm continues this process for all possible starting positions and returns the maximum length found, or -1 if no valid self-contained substring exists.

The time complexity is O(n²) where n is the length of the string, as we potentially examine each substring starting from each character's first occurrence. The space complexity is O(k) where k is the number of unique characters in the string.

Example Walkthrough

Let's walk through the solution with the string s = "abcabc".

Step 1: Build first and last occurrence maps

• Iterate through the string to record positions:
  • 'a': first = 0, last = 3
  • 'b': first = 1, last = 4
  • 'c': first = 2, last = 5

Step 2: Try each character's first occurrence as a starting point

Starting from 'a' (position 0):

• Initialize: i = 0, mx = 3 (last position of 'a')
• Position 0: character 'a'
  • First occurrence of 'a' = 0 (not < 0, so continue)
  • Update mx = max(3, 3) = 3
  • Check: mx (3) ≠ j (0), continue
• Position 1: character 'b'
  • First occurrence of 'b' = 1 (not < 0, so continue)
  • Update mx = max(3, 4) = 4
  • Check: mx (4) ≠ j (1), continue
• Position 2: character 'c'
  • First occurrence of 'c' = 2 (not < 0, so continue)
  • Update mx = max(4, 5) = 5
  • Check: mx (5) ≠ j (2), continue
• Position 3: character 'a'
  • First occurrence of 'a' = 0 (not < 0, so continue)
  • Update mx = max(5, 3) = 5
  • Check: mx (5) ≠ j (3), continue
• Position 4: character 'b'
  • First occurrence of 'b' = 1 (not < 0, so continue)
  • Update mx = max(5, 4) = 5
  • Check: mx (5) ≠ j (4), continue
• Position 5: character 'c'
  • First occurrence of 'c' = 2 (not < 0, so continue)
  • Update mx = max(5, 5) = 5
  • Check: mx (5) = j (5) ✓ and 5 - 0 + 1 = 6 = n, not valid (equals entire string)

Starting from 'b' (position 1):

• Initialize: i = 1, mx = 4 (last position of 'b')
• Position 1: character 'b'
  • First occurrence of 'b' = 1 (not < 1, so continue)
  • Update mx = max(4, 4) = 4
  • Check: mx (4) ≠ j (1), continue
• Position 2: character 'c'
  • First occurrence of 'c' = 2 (not < 1, so continue)
  • Update mx = max(4, 5) = 5
  • Check: mx (5) ≠ j (2), continue
• Position 3: character 'a'
  • First occurrence of 'a' = 0 (0 < 1) ✗ Break!
  • Character 'a' appears before our start position, invalid

Starting from 'c' (position 2):

• Initialize: i = 2, mx = 5 (last position of 'c')
• Position 2: character 'c'
  • First occurrence of 'c' = 2 (not < 2, so continue)
  • Update mx = max(5, 5) = 5
  • Check: mx (5) ≠ j (2), continue
• Position 3: character 'a'
  • First occurrence of 'a' = 0 (0 < 2) ✗ Break!
  • Character 'a' appears before our start position, invalid

Step 3: Return result No valid self-contained substring was found, so return -1.

Let's try another example where a valid substring exists: s = "abcdefabc"

Step 1: Build maps

• 'a': first = 0, last = 6
• 'b': first = 1, last = 7
• 'c': first = 2, last = 8
• 'd': first = 3, last = 3
• 'e': first = 4, last = 4
• 'f': first = 5, last = 5

Step 2: Try starting from 'd' (position 3):

• Initialize: i = 3, mx = 3
• Position 3: character 'd'
  • First occurrence = 3 (not < 3, continue)
  • Update mx = max(3, 3) = 3
  • Check: mx (3) = j (3) ✓ and 3 - 3 + 1 = 1 < 9 ✓
  • Found valid substring "d" with length 1

Continuing to check 'e' (position 4):

• Similar process yields "e" with length 1

Continuing to check 'f' (position 5):

• Similar process yields "f" with length 1

The longest self-contained substring has length 1 (any of "d", "e", or "f").

Time and Space Complexity

Time Complexity: O(n × |Σ|)

The algorithm consists of two main parts:

1. The first loop iterates through the string once to build the first and last dictionaries, taking O(n) time.
2. The second nested loop structure:
   • The outer loop iterates through each unique character in the first dictionary, which can be at most |Σ| characters
   • For each character, the inner loop can iterate up to n positions in the worst case
   • Therefore, this part takes O(|Σ| × n) time

The overall time complexity is O(n) + O(|Σ| × n) = O(n × |Σ|), where n is the length of string s and |Σ| represents the size of the character set (26 for lowercase letters).

Space Complexity: O(|Σ|)

The algorithm uses:

• Two dictionaries first and last to store the first and last occurrence indices of each character
• Each dictionary can store at most |Σ| key-value pairs (one for each unique character in the string)
• A few additional variables (ans, n, mx, etc.) that use constant space

Therefore, the space complexity is O(|Σ|), where |Σ| = 26 for lowercase English letters.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Breaking Early When Character Appears Before Start Position

A critical pitfall is forgetting to break the inner loop when encountering a character that has already appeared before the current starting position. This would lead to incorrect results by considering invalid substrings.

Incorrect Implementation:

for current_index in range(start_index, string_length):  current_char = s[current_index]  char_first = first_occurrence[current_char]  char_last = last_occurrence[current_char]   # MISSING: Should break if char_first < start_index   required_end = max(required_end, char_last)  # ... rest of code

Why This Fails: Without the break condition, the algorithm would continue processing even when it encounters characters that violate the self-contained property. For example, with s = "abcabc", when starting from index 3 (second 'a'), it would incorrectly consider the substring "abc" at indices 3-5 as valid, even though 'a', 'b', 'c' also appear at indices 0-2.

Solution: Always include the break condition:

if char_first < start_index:  break

2. Incorrect Validation of Substring Length

Another common mistake is using <= instead of < when checking if the substring length is less than the total string length.

Incorrect Implementation:

if required_end == current_index and current_index - start_index + 1 <= string_length:  max_length = max(max_length, current_index - start_index + 1)

Why This Fails: Using <= would allow the entire string to be considered as a valid self-contained substring, which violates the constraint that t != s. This would return the length of the entire string instead of -1 for strings like s = "aaa" where no proper self-contained substring exists.

Solution: Use strict inequality:

if required_end == current_index and current_index - start_index + 1 < string_length:  max_length = max(max_length, current_index - start_index + 1)

3. Not Initializing required_end Correctly

Forgetting to initialize required_end with the last occurrence of the starting character can cause the algorithm to miss valid substrings.

Incorrect Implementation:

for char, start_index in first_occurrence.items():  required_end = start_index # Wrong: should be last_occurrence[char]  # ... rest of code

Why This Fails: If a character appears multiple times, we must ensure all its occurrences are included in the substring. Starting with required_end = start_index would fail to account for later occurrences of the starting character itself.

Solution: Initialize with the last occurrence of the starting character:

required_end = last_occurrence[char]