Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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^4
  • s consists only of lowercase English letters.

Solution

Method 1 – Sliding Window with HashSet

Intuition

A substring is self-contained if all its characters are unique and do not appear outside the substring. We can use a sliding window to check all substrings, but to be efficient, we can precompute the first and last occurrence of each character and only consider substrings where all characters’ first and last occurrence are within the window.

Approach

  1. Precompute the first and last occurrence of each character in s.
  2. For each possible substring s[l:r] (with r-l < n), check:
    • For every character in the substring, its first and last occurrence must be within [l, r).
    • The substring must not be the whole string.
  3. Use a sliding window and hash set to check uniqueness and containment efficiently.
  4. Track the maximum length found.
  5. Return the maximum length, or -1 if none.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int longestSelfContainedSubstring(string s) {
        int n = s.size(), ans = -1;
        vector<int> first(26, n), last(26, -1);
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            first[c] = min(first[c], i);
            last[c] = max(last[c], i);
        }
        for (int l = 0; l < n; ++l) {
            unordered_set<char> seen;
            for (int r = l; r < n; ++r) {
                char c = s[r];
                if (seen.count(c)) break;
                seen.insert(c);
                int idx = c - 'a';
                if (first[idx] < l || last[idx] > r) continue;
                if (r - l + 1 < n) ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func longestSelfContainedSubstring(s string) int {
    n := len(s)
    first := make([]int, 26)
    last := make([]int, 26)
    for i := range first {
        first[i] = n
        last[i] = -1
    }
    for i, c := range s {
        idx := int(c - 'a')
        if i < first[idx] { first[idx] = i }
        if i > last[idx] { last[idx] = i }
    }
    ans := -1
    for l := 0; l < n; l++ {
        seen := map[byte]bool{}
        for r := l; r < n; r++ {
            c := s[r]
            if seen[c] { break }
            seen[c] = true
            idx := int(c - 'a')
            if first[idx] < l || last[idx] > r { continue }
            if r-l+1 < n && r-l+1 > ans { ans = r-l+1 }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int longestSelfContainedSubstring(String s) {
        int n = s.length(), ans = -1;
        int[] first = new int[26], last = new int[26];
        Arrays.fill(first, n);
        Arrays.fill(last, -1);
        for (int i = 0; i < n; i++) {
            int idx = s.charAt(i) - 'a';
            first[idx] = Math.min(first[idx], i);
            last[idx] = Math.max(last[idx], i);
        }
        for (int l = 0; l < n; l++) {
            Set<Character> seen = new HashSet<>();
            for (int r = l; r < n; r++) {
                char c = s.charAt(r);
                if (seen.contains(c)) break;
                seen.add(c);
                int idx = c - 'a';
                if (first[idx] < l || last[idx] > r) continue;
                if (r - l + 1 < n) ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun longestSelfContainedSubstring(s: String): Int {
        val n = s.length
        val first = IntArray(26) { n }
        val last = IntArray(26) { -1 }
        for (i in s.indices) {
            val idx = s[i] - 'a'
            first[idx] = minOf(first[idx], i)
            last[idx] = maxOf(last[idx], i)
        }
        var ans = -1
        for (l in 0 until n) {
            val seen = mutableSetOf<Char>()
            for (r in l until n) {
                val c = s[r]
                if (c in seen) break
                seen.add(c)
                val idx = c - 'a'
                if (first[idx] < l || last[idx] > r) continue
                if (r - l + 1 < n) ans = maxOf(ans, r - l + 1)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def longestSelfContainedSubstring(self, s: str) -> int:
        n = len(s)
        first = {c: n for c in set(s)}
        last = {c: -1 for c in set(s)}
        for i, c in enumerate(s):
            first[c] = min(first[c], i)
            last[c] = max(last[c], i)
        ans = -1
        for l in range(n):
            seen = set()
            for r in range(l, n):
                c = s[r]
                if c in seen:
                    break
                seen.add(c)
                if first[c] < l or last[c] > r:
                    continue
                if r - l + 1 < n:
                    ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn longest_self_contained_substring(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut first = vec![n; 26];
        let mut last = vec![-1; 26];
        for (i, &c) in s.iter().enumerate() {
            let idx = (c - b'a') as usize;
            if i < first[idx] { first[idx] = i; }
            if i as i32 > last[idx] { last[idx] = i as i32; }
        }
        let mut ans = -1;
        for l in 0..n {
            let mut seen = std::collections::HashSet::new();
            for r in l..n {
                let c = s[r];
                if !seen.insert(c) { break; }
                let idx = (c - b'a') as usize;
                if first[idx] < l || last[idx] > r as i32 { continue; }
                if r - l + 1 < n && (r - l + 1) as i32 > ans { ans = (r - l + 1) as i32; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    longestSelfContainedSubstring(s: string): number {
        const n = s.length;
        const first: Record<string, number> = {};
        const last: Record<string, number> = {};
        for (let i = 0; i < n; i++) {
            const c = s[i];
            if (!(c in first)) first[c] = i;
            last[c] = i;
        }
        let ans = -1;
        for (let l = 0; l < n; l++) {
            const seen = new Set<string>();
            for (let r = l; r < n; r++) {
                const c = s[r];
                if (seen.has(c)) break;
                seen.add(c);
                if (first[c] < l || last[c] > r) continue;
                if (r - l + 1 < n) ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of s. Each substring is checked in quadratic time.
  • 🧺 Space complexity: O(n), for storing first/last occurrence and sets.