Max Repeated Substring with Wildcards
MediumStrings · Amazon
A string is a square if it has even length 2h and its first h characters equal its last h characters, for example "abab" or "zz".
You are given a string s made of lowercase letters and '?'. Each '?' may be replaced by any lowercase letter you like (different '?' can become different letters). Return the maximum length of a contiguous substring of s that can be turned into a square by some choice of replacements. If no substring of length at least 2 can be made a square, return 0.
Example 1
- Input:
- s = 'abcab?ab'
- Output:
- 6
- Explanation
- The substring
cab?ab(positions 2 to 7) becomescabcabby replacing the?withc, so length 6 works. The whole string cannot: its halvesabcaandb?abalready clash in the first position (a versus b).
Example 2
- Input:
- s = 'a??ba'
- Output:
- 4
- Explanation
a??bbecomesababby choosingbthenafor the two question marks, giving length 4; length 5 is odd and cannot be a square.
Example 3
- Input:
- s = 'xyz'
- Output:
- 0
- Explanation
- No two characters can be made equal (there is no
?), so even length 2 is impossible.
Constraints
1 <= s.length <= 2000sconsists of lowercase English letters and'?'