In this guide, you will get 3557. Find Maximum Number of Non Intersecting Substrings LeetCode Solution with the best time and space complexity. The solution to Find Maximum Number of Non Intersecting Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Maximum Number of Non Intersecting Substrings
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.
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 * 105
word consists only of lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3557. Find Maximum Number of Non Intersecting Substrings LeetCode Solution in C++
class Solution {
public:
int maxSubstrings(string word) {
int ans = 0;
unordered_map<char, int> firstSeen;
for (int i = 0; i < word.length(); ++i) {
const char c = word[i];
if (!firstSeen.contains(c)) {
firstSeen[c] = i;
} else if (i - firstSeen[c] + 1 >= 4) {
++ans;
firstSeen.clear();
}
}
return ans;
}
}; /* code provided by PROGIEZ */
3557. Find Maximum Number of Non Intersecting Substrings LeetCode Solution in Java
class Solution {
public int maxSubstrings(String word) {
int ans = 0;
Map<Character, Integer> firstSeen = new HashMap<>();
for (int i = 0; i < word.length(); ++i) {
final char c = word.charAt(i);
if (!firstSeen.containsKey(c)) {
firstSeen.put(c, i);
} else if (i - firstSeen.get(c) + 1 >= 4) {
++ans;
firstSeen.clear();
}
}
return ans;
}
} // code provided by PROGIEZ
3557. Find Maximum Number of Non Intersecting Substrings LeetCode Solution in Python
class Solution:
def maxSubstrings(self, word: str) -> int:
ans = 0
firstSeen = {}
for i, c in enumerate(word):
if c not in firstSeen:
firstSeen[c] = i
elif i - firstSeen[c] + 1 >= 4:
ans += 1
firstSeen.clear()
return ans # code by PROGIEZ
