LeetCode-in-Java
3557. Find Maximum Number of Non Intersecting Substrings
Medium
You are given a string word.
Return the maximum number of non-intersecting **substring** of word that are at least four characters long and start and end with the same letter.
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
import java.util.Arrays;
public class Solution {
public int maxSubstrings(String s) {
int[] prev = new int[26];
int r = 0;
Arrays.fill(prev, -1);
for (int i = 0; i < s.length(); ++i) {
int j = s.charAt(i) - 'a';
if (prev[j] != -1 && i - prev[j] + 1 >= 4) {
++r;
Arrays.fill(prev, -1);
} else if (prev[j] == -1) {
prev[j] = i;
}
}
return r;
}
}