Find Longest Self-Contained Substring — DSA

Problem#

A substring s[l..r] is “self-contained” if it doesn’t span the entire string and every letter appearing in s[l..r] does not appear in s outside [l, r]. Return the maximum length of such a substring, or -1 if none exists. This is an curriculum variant.

Examples#

s = "abba" → 2 ("bb" — b only appears inside).
s = "abcabc" → -1 (every letter spans the entire string).
s = "abab" → -1.

Constraints#

1 <= s.length <= 5 * 10^4, lowercase letters.

Hints#

Hint 1

For each letter, precompute its first and last occurrence in s.

Hint 2

A candidate [l, r] is valid iff for every letter c appearing in [l, r], first[c] >= l and last[c] <= r.

Approach#

Compute first[c] and last[c] for every letter. Walk each starting index l. Maintain r as the running max of last[c] for letters seen in [l, r]. Extend r while needed; if at any point a letter c in [l, r] has first[c] < l, this start is invalid — skip. Otherwise when r stabilizes and r - l + 1 < n, update the answer.

Solution#

class Solution {
public:
    int maxSubstringLength(string s) {
        int n = s.size();
        vector<int> first(26, -1), last(26, -1);
        for (int i = 0; i < n; ++i) {
            if (first[s[i] - 'a'] == -1) first[s[i] - 'a'] = i;
            last[s[i] - 'a'] = i;
        }
        int ans = -1;
        for (int c = 0; c < 26; ++c) {
            int l = first[c];
            if (l == -1) continue;
            int r = last[c];
            bool ok = true;
            for (int i = l; i <= r && ok; ++i) {
                int ch = s[i] - 'a';
                if (first[ch] < l) { ok = false; break; }
                if (last[ch] > r) r = last[ch];
            }
            if (ok && r - l + 1 < n) ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

func maxSubstringLength(s string) int {
    n := len(s)
    first := make([]int, 26)
    last := make([]int, 26)
    for i := range first {
        first[i] = -1
        last[i] = -1
    }
    for i := 0; i < n; i++ {
        c := s[i] - 'a'
        if first[c] == -1 {
            first[c] = i
        }
        last[c] = i
    }
    ans := -1
    for c := 0; c < 26; c++ {
        l := first[c]
        if l == -1 {
            continue
        }
        r := last[c]
        ok := true
        for i := l; i <= r; i++ {
            ch := s[i] - 'a'
            if first[ch] < l {
                ok = false
                break
            }
            if last[ch] > r {
                r = last[ch]
            }
        }
        if ok && r-l+1 < n {
            if r-l+1 > ans {
                ans = r - l + 1
            }
        }
    }
    return ans
}

class Solution:
    def maxSubstringLength(self, s: str) -> int:
        n = len(s)
        first = [-1] * 26
        last = [-1] * 26
        for i, ch in enumerate(s):
            c = ord(ch) - ord('a')
            if first[c] == -1:
                first[c] = i
            last[c] = i
        ans = -1
        for c in range(26):
            l = first[c]
            if l == -1:
                continue
            r = last[c]
            ok = True
            i = l
            while i <= r:
                ch = ord(s[i]) - ord('a')
                if first[ch] < l:
                    ok = False
                    break
                if last[ch] > r:
                    r = last[ch]
                i += 1
            if ok and r - l + 1 < n:
                ans = max(ans, r - l + 1)
        return ans

function maxSubstringLength(s) {
    const n = s.length;
    const first = new Array(26).fill(-1);
    const last = new Array(26).fill(-1);
    const A = 'a'.charCodeAt(0);
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - A;
        if (first[c] === -1) first[c] = i;
        last[c] = i;
    }
    let ans = -1;
    for (let c = 0; c < 26; c++) {
        const l = first[c];
        if (l === -1) continue;
        let r = last[c];
        let ok = true;
        for (let i = l; i <= r; i++) {
            const ch = s.charCodeAt(i) - A;
            if (first[ch] < l) { ok = false; break; }
            if (last[ch] > r) r = last[ch];
        }
        if (ok && r - l + 1 < n) {
            ans = Math.max(ans, r - l + 1);
        }
    }
    return ans;
}

class Solution {
    public int maxSubstringLength(String s) {
        int n = s.length();
        int[] first = new int[26];
        int[] last = new int[26];
        Arrays.fill(first, -1);
        Arrays.fill(last, -1);
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] == -1) first[c] = i;
            last[c] = i;
        }
        int ans = -1;
        for (int c = 0; c < 26; c++) {
            int l = first[c];
            if (l == -1) continue;
            int r = last[c];
            boolean ok = true;
            for (int i = l; i <= r; i++) {
                int ch = s.charAt(i) - 'a';
                if (first[ch] < l) { ok = false; break; }
                if (last[ch] > r) r = last[ch];
            }
            if (ok && r - l + 1 < n) {
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}

function maxSubstringLength(s: string): number {
    const n = s.length;
    const first: number[] = new Array(26).fill(-1);
    const last: number[] = new Array(26).fill(-1);
    const A = 'a'.charCodeAt(0);
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - A;
        if (first[c] === -1) first[c] = i;
        last[c] = i;
    }
    let ans = -1;
    for (let c = 0; c < 26; c++) {
        const l = first[c];
        if (l === -1) continue;
        let r = last[c];
        let ok = true;
        for (let i = l; i <= r; i++) {
            const ch = s.charCodeAt(i) - A;
            if (first[ch] < l) { ok = false; break; }
            if (last[ch] > r) r = last[ch];
        }
        if (ok && r - l + 1 < n) {
            ans = Math.max(ans, r - l + 1);
        }
    }
    return ans;
}

Editorial#

We anchor candidate windows at each letter’s first occurrence, then grow r to cover every occurrence of every letter touched. If any letter inside the window has its first occurrence before l, the window cannot be self-contained — every letter must be entirely inside. Excluding the case where the window equals the whole string handles the “less than the entire string” constraint.

Complexity#

Time: O(26 * N).
Space: O(1) for the per-letter arrays.

Concept revision#

Partition Labels