875838. Maximize partitions in a String
Easy
Maximize partitions in a String
Slug: maximize-partitions-in-a-string
Difficulty: Easy
Id: 875838
Topic Tags: None
Company Tags: None
Summary
Given a string, the task is to partition the string into maximum number of substrings such that each substring contains at most one distinct character. The problem can be viewed as finding the maximum number of partitions in a string.
Detailed Explanation
The approach to solve this problem involves iterating through the string and keeping track of the current character. When we encounter a new character, we increment our partition count.
Here is the step-by-step breakdown:
- Initialize a variable
partitionsto 0. - Iterate through the input string. For each character:
- If it's different from the previous one (or this is the first character), increment
partitions.
- If it's different from the previous one (or this is the first character), increment
- Return the maximum number of partitions found.
The time complexity for this solution is O(n), where n is the length of the input string, as we are making a single pass through the string. The space complexity is O(1), as we are only using a constant amount of space to store our partition count.
Optimized Solutions
Java
public int maxPartitions(String str) {
if (str == null || str.isEmpty()) {
return 0;
}
int partitions = 0;
char prevChar = str.charAt(0);
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) != prevChar) {
partitions++;
prevChar = str.charAt(i);
}
}
return partitions + 1;
}