Longest Self-Sufficient Substring
MediumStrings · Amazon
A substring t of s is self-sufficient if no character that appears in t appears anywhere in s outside t. In other words, for every letter in t, all of its occurrences in s lie inside t.
Return the length of the longest self-sufficient substring of s that is not the entire string s. If there is no such substring, return -1.
Example 1
- Input:
- s = 'abacdcfgf'
- Output:
- 6
- Explanation
aba,cdcandfgfare each self-sufficient, and so is any run of consecutive blocks.abacdc(length 6) is the longest one that is not the whole string;cdcfgfties it.
Example 2
- Input:
- s = 'abcab'
- Output:
- 1
- Explanation
- Any substring containing
aorbmust include positions 0 through 4, which is the whole string. That leaves onlyc, of length 1.
Example 3
- Input:
- s = 'zzz'
- Output:
- -1
- Explanation
- A substring containing
zmust contain all three z's, which is the whole string, so no valid substring exists.
Constraints
2 <= s.length <= 5 * 10^4sconsists of lowercase English letters