| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
困难 |
|
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 * 104sconsists only of lowercase English letters.
我们注意到，满足条件的子串的开头一定是某个字符第一次出现的位置。
因此，我们可以用两个数组或哈希表 first 和 last 分别记录每个字符第一次和最后一次出现的位置。
接下来，我们枚举每个字符 c，假设 c 第一次出现的位置是
最后返回答案即可。
时间复杂度
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 ansclass 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;
}