Problem Description

Given a string s, the 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 is not equal to 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.

Intuition

To solve this problem, we need to identify a substring t such that every character in t is unique to that substring and not found elsewhere in the string s. Initially, we recognize that for a substring to be self-contained, it should satisfy that none of its characters appear outside it in s.

The strategy involves tracking the first and last occurrence of each character in the string. Using two dictionaries, first and last, we store the earliest and latest appearance of every character, respectively. This helps understand the possible boundaries of our potential self-contained substrings.

Next, we iterate through each unique character, marking the starting position for a possible self-contained substring. From this position, we attempt to expand the substring by checking each subsequent character. If any character's initial occurrence is before our starting point, it means that character is shared with the portion of s we've already considered, so the current expansion must halt.

For valid candidates, we keep expanding until reaching a maximum boundary, determined by the latest occurrence (last) of any characters in our current substring. Anytime we find a plausible self-contained substring (ensuring it's shorter than s itself), we update our answer with its length if it exceeds the previous maximum found.

Finally, the answer will reflect the length of the longest valid self-contained substring, or -1 if none exist.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

To implement the solution for finding the length of the longest self-contained substring, we will follow a structured approach using hash tables to efficiently track character positions.

Step-by-Step Implementation

1. Data Structures:

   • Use two dictionaries: first and last to store the first and last occurrence indexes of each character in the string s.

2. Populating Occurrence Dictionaries:

   • Traverse the string s while updating first and last for each character. first[c] should store the earliest index where character c appears, and last[c] stores the latest index of c. This can be done by iterating through the string with an index.

3. Initialization:

   • Begin with ans = -1 to handle the case when no valid substring is found. This variable will hold the maximum length of a self-contained substring.

4. Enumerating Possible Substrings:

   • For every character c in first, assume this character's first occurrence is the starting index i of a potential substring.
   • Initialize mx as last[c] to keep track of the farthest index up to which the current substring can extend without repeating characters outside it.

5. Expanding the Substring:

   • Start extending the substring from i towards the right. For each character at position j, check if the first occurrence a of the current character is before i. If it is, break out because it means the character belongs partly to a previously processed section of the string.

6. Updating Maximum Boundary:

   • Update mx with the largest occurrence index encountered (b = last[s[j]]) as we iterate.
   • If mx equals j (indicating the end of our current valid consideration) and j - i + 1 is less than the length of s (to ensure it's not the whole string), update ans with the current substring's length using ans = max(ans, j - i + 1).

7. Result:

   • After considering all possible starting points, ans will provide the length of the longest self-contained substring, or it will remain as -1 if no such substring exists.

By carefully managing the first and last occurrence of characters and iteratively checking each potential substring, this approach efficiently identifies the longest self-contained portion of the string.

Example Walkthrough

Let's walk through an example using the string s = "abacded" to identify the longest self-contained substring.

1. Data Structures: We begin by initializing two dictionaries, first and last, to track the first and last occurrences of each character in the string.

   • After traversing s, the dictionaries are populated as follows:
     • first = {'a': 0, 'b': 1, 'c': 2, 'd': 4, 'e': 5}
     • last = {'a': 2, 'b': 1, 'c': 2, 'd': 6, 'e': 5}

2. Initialization: We set ans = -1 to start with, indicating that we haven't found a valid self-contained substring yet.

3. Enumerating Possible Substrings: We iterate over the characters using their first occurrence as potential starting points.

   • Starting with character 'a' at index 0:
     • Set mx = 2 (the last occurrence of 'a').

4. Expanding the Substring:

   • Extend from index 0 and check each subsequent character:
     • At index 1, the character 'b' has its first occurrence at 1, which is not before 0. Update mx = 1.
     • At index 2, the character 'a' itself, confirms end of the potential substring (mx = 2).
   • The length is 2 - 0 + 1 = 3, which is less than the length of s. Update ans = max(-1, 3) = 3.

5. Continuing with other characters:

   • Starting with 'b' at index 1:
     • Set mx = 1. However, 'a' reappears in subsequent indices (2), so this expansion is halted.
   • Starting with 'c' at index 2:
     • Set mx = 2. No further valid expansion found.
   • Starting with 'd' at index 4:
     • Set mx = 6. Check indices 4 to 6, the substring "ded" found with length 3 but equal to current ans.
   • Starting with 'e' at index 5:
     • The character d appears again later in the string, halting potential expansions.

6. Result: After exploring all possible starting points, the longest self-contained substring is of length 3, given by the substring "aba" starting at index 0.

This walkthrough highlights the method of using dictionaries to track character positions, managing indices efficiently, and iterating through potential substrings systematically for the solution.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n × |\Sigma|), where n is the length of the string s, and |\Sigma| represents the size of the character set. In this case, the character set consists of lowercase letters, resulting in |\Sigma| = 26.

The primary reason for this complexity is the nested loops: the outer loop iterates over each character (unique characters, thus |\Sigma| iterations), and the inner loop iterates over each subsequent character in the string (up to n iterations).

The space complexity is O(|\Sigma|). This arises from the use of the first and last dictionaries, each of which stores at most one entry for every character in the character set, leading to constant space usage given |\Sigma| = 26.

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