3857. Find Maximum Number Of Non Intersecting Substrings¶
3857. Find Maximum Number of Non Intersecting Substrings
Medium
You are given a string word.
Return the maximum number of non-intersecting substrings of word that are at least four characters long and start and end with the same letter.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: word = "abcdeafdef"
Output: 2
Explanation:
The two substrings are "abcdea" and "fdef".
Example 2:
Input: word = "bcdaaaab"
Output: 1
Explanation:
The only substring is "aaaa". Note that we cannot also choose "bcdaaaab" since it intersects with the other substring.
Constraints:
1 <= word.length <= 2 * 105wordconsists only of lowercase English letters.
Solution¶
class Solution {
public int maxSubstrings(String s) {
int n = s.length();
int occurred[] = new int[26];
Arrays.fill(occurred, -1);
int res = 0;
for (int i = n - 1; i >= 0; i--) {
char ch = s.charAt(i);
boolean isSeen = occurred[ch - 'a'] != -1;
if (isSeen) {
if (occurred[ch - 'a'] - i + 1 >= 4) {
res++;
Arrays.fill(occurred, -1);
}
}
else occurred[ch - 'a'] = i;
}
return res;
}
}
Complexity Analysis¶
- Time Complexity: O(?)
- Space Complexity: O(?)
Explanation¶
[Add detailed explanation here]