3104. Find Longest Self-Contained Substring 🔒

Description

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.

Example 1:

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:

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:

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

Solutions

Solution 1: Enumeration

Thinking

A self-contained substring must contain every occurrence of each of its characters and cannot be the whole string. Checking every interval against \(26\) first/last positions is \(O(n^2|\Sigma|)\) and too heavy.

A valid left endpoint must be some character's first occurrence: extending further left only adds a new character or an earlier copy. With at most \(26\) letters the candidate starts are few.

Record each character's first and last index, enumerate left endpoint \(i\), and walk \(j\) rightward while tracking the farthest cover \(mx\). Stop if a character first appears before \(i\); when \(mx=j\) and the interval is proper, update the longest length.

We notice that the start of a substring that meets the conditions must be the position where a character appears for the first time.

Therefore, we can use two arrays or hash tables first and last to record the positions where each character appears for the first time and the last time, respectively.

Next, we enumerate each character c. Suppose the position where c first appears is \(i\), and the position where it last appears is \(mx\). Then we can start traversing from \(i\). For each position \(j\), we find the position \(a\) where \(s[j]\) first appears and the position \(b\) where it last appears. If \(a < i\), it means that \(s[j]\) is on the left of \(c\), which does not meet the enumeration conditions, and we can exit the loop directly. Otherwise, we update \(mx = \max(mx, b)\). If \(mx = j\) and \(j - i + 1 < n\), we update the answer to \(ans = \max(ans, j - i + 1)\).

Finally, return the answer.

Python3JavaC++GoTypeScript

class Solution:
    def maxSubstringLength(self, s: str) -> int:
        first, last = {}, {}
        for i, c in enumerate(s):
            if c not in first:
                first[c] = i
            last[c] = i
        ans, n = -1, len(s)
        for c, i in first.items():
            mx = last[c]
            for j in range(i, n):
                a, b = first[s[j]], last[s[j]]
                if a < i:
                    break
                mx = max(mx, b)
                if mx == j and j - i + 1 < n:
                    ans = max(ans, j - i + 1)
        return ans

class Solution {
    public int maxSubstringLength(String s) {
        int[] first = new int[26];
        int[] last = new int[26];
        Arrays.fill(first, -1);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int j = s.charAt(i) - 'a';
            if (first[j] == -1) {
                first[j] = i;
            }
            last[j] = i;
        }
        int ans = -1;
        for (int k = 0; k < 26; ++k) {
            int i = first[k];
            if (i == -1) {
                continue;
            }
            int mx = last[k];
            for (int j = i; j < n; ++j) {
                int a = first[s.charAt(j) - 'a'];
                int b = last[s.charAt(j) - 'a'];
                if (a < i) {
                    break;
                }
                mx = Math.max(mx, b);
                if (mx == j && j - i + 1 < n) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxSubstringLength(string s) {
        vector<int> first(26, -1);
        vector<int> last(26);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int j = s[i] - 'a';
            if (first[j] == -1) {
                first[j] = i;
            }
            last[j] = i;
        }
        int ans = -1;
        for (int k = 0; k < 26; ++k) {
            int i = first[k];
            if (i == -1) {
                continue;
            }
            int mx = last[k];
            for (int j = i; j < n; ++j) {
                int a = first[s[j] - 'a'];
                int b = last[s[j] - 'a'];
                if (a < i) {
                    break;
                }
                mx = max(mx, b);
                if (mx == j && j - i + 1 < n) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

func maxSubstringLength(s string) int {
    first := [26]int{}
    last := [26]int{}
    for i := range first {
        first[i] = -1
    }
    n := len(s)
    for i, c := range s {
        j := int(c - 'a')
        if first[j] == -1 {
            first[j] = i
        }
        last[j] = i
    }
    ans := -1
    for k := 0; k < 26; k++ {
        i := first[k]
        if i == -1 {
            continue
        }
        mx := last[k]
        for j := i; j < n; j++ {
            a, b := first[s[j]-'a'], last[s[j]-'a']
            if a < i {
                break
            }
            mx = max(mx, b)
            if mx == j && j-i+1 < n {
                ans = max(ans, j-i+1)
            }
        }
    }
    return ans
}

function maxSubstringLength(s: string): number {
    const first: number[] = Array(26).fill(-1);
    const last: number[] = Array(26).fill(0);
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        const j = s.charCodeAt(i) - 97;
        if (first[j] === -1) {
            first[j] = i;
        }
        last[j] = i;
    }
    let ans = -1;
    for (let k = 0; k < 26; ++k) {
        const i = first[k];
        if (i === -1) {
            continue;
        }
        let mx = last[k];
        for (let j = i; j < n; ++j) {
            const a = first[s.charCodeAt(j) - 97];
            if (a < i) {
                break;
            }
            const b = last[s.charCodeAt(j) - 97];
            mx = Math.max(mx, b);
            if (mx === j && j - i + 1 < n) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
}

3104. Find Longest Self-Contained Substring 🔒

Description

Solutions

Solution 1: Enumeration

Comments