1422. Maximum Score After Splitting a String
Problem Description
In this problem, we are given a string s
consisting of characters '0' and '1'. Our goal is to split this string into two non-empty parts, a left and a right substring, such that the score obtained from the split is maximized. The score is calculated as the number of '0' characters in the left substring added to the number of '1' characters in the right substring. We need to determine the maximum score we can achieve by splitting the string s
. It's important to note that the split must result in non-empty substrings, which means we can split the string anywhere between the first and last character.
Intuition
To solve this problem, we need to understand that the split will always be between two characters in the string. In terms of index i
, the left substring will include characters from index 0
to i
, and the right substring will include characters from index i+1
to the end. Our goal is to maximize the sum of zeros in the left substring and ones in the right substring.
A straightforward approach would be to check all possible splits and calculate the score for each, but that would be inefficient. Instead, we can take advantage of the fact that any split only moves one character from one substring to the other, thus changing the score by either 1 or -1. This allows us to iteratively calculate the score for all possible splits in a single pass through the string after an initial count.
Here's the step-by-step intuition:
- Start by calculating the initial score, which is the number of '0's in the first position plus the number of '1's in the rest of the string (since the first character must be in the left substring for it to be non-empty).
- Initialize the maximum score
ans
with this initial score. - Iterate over the string starting from the second character to the second-to-last character, updating the current score
t
and maximum scoreans
as follows:- If we find a '0', it means moving the split to the right would bring one more '0' to the left substring, so we increase
t
by 1. - If we find a '1', it means moving the split to the right would take one '1' out of the right substring, so we decrease
t
by 1. - After each update, compare
t
with the currentans
and updateans
ift
is higher.
- If we find a '0', it means moving the split to the right would bring one more '0' to the left substring, so we increase
- Once we've considered all splits, the
ans
variable will hold the maximum score possible.
This solution has a linear time complexity because we go through the string only once after the initial count, making it an efficient approach.
Solution Approach
The solution utilizes a simple yet efficient algorithm that takes advantage of the cumulative property of scores during the split process. Let's delve into the key aspects of the implementation:
-
Initializing Scores:
- The initial score
t
is computed by checking if the first character is '0' and adding it to the count of '1's in the rest of the string. This is because we want all '0's to be in the left substring and '1's to be in the right one to maximize the score. - The Python expression
(s[0] == '0')
returnsTrue
if the first character is '0' andFalse
otherwise. SinceTrue
equates to1
andFalse
to0
in Python, this expression conveniently adds1
to the count if the first character is '0'. - The count of '1's in the right substring is calculated using
s[1:].count('1')
, wheres[1:]
is the substring excluding the first character.
- The initial score
-
Iterating over Characters:
- A
for
loop is used to iterate through each character in the string starting from index 1 and ending at the second-last character, since we are only interested in valid splits (non-empty left and right substrings). - During each iteration, the variable
t
is updated to reflect the new score if the split were to occur right after the current character. Ifs[i]
is '0',t
is incremented by 1 because we'd have one more '0' in the left substring. Conversely, ifs[i]
is '1',t
is decremented by 1 because we'd have one less '1' in the right substring.
- A
-
Updating Maximum Score:
- The maximum score so far is kept in the variable
ans
. After each score update,ans
is set to the maximum of itself and the current scoret
by executingans = max(ans, t)
.
- The maximum score so far is kept in the variable
-
Return Final Score:
- After the loop completes, the maximum score
ans
is returned.
- After the loop completes, the maximum score
By using a single pass through the string and updating scores incrementally, this solution achieves a time complexity of O(n), where n is the length of the string. The space complexity is O(1) since only a fixed number of variables are used.
We use no additional data structures; instead, we capitalize on the fact that iterating over the string while tracking the current score and the maximum score suffices to solve the problem. The pattern used here involves greedy local optimizations at each character index that leads to a global optimization, i.e., the maximum score.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example string s = "011101"
to illustrate the solution approach step-by-step:
-
Initializing Scores:
- We start by calculating the initial score
t
for the first possible split, which will have all characters in the left substring except the first one on the right side. - With our example, the first character is '0', so according to the logic,
(s[0] == '0')
will beTrue
, and thust
starts at 1. - Then, we count the number of '1's in the rest of the string (
"11101"
), which is 4. So, the initial scoret
is1 + 4 = 5
. - We also initialize the maximum score
ans
to this initial value,ans = 5
.
- We start by calculating the initial score
-
Iterating over Characters:
- We start processing the string from the second character to the second-to-last character.
- As we move to the next character, which is '1', the score
t
does not change as per the rule because '1' is already in the right substring. Therefore,t
remains 5 andans
remains 5. - The next character is '1' again, and nothing changes for the same reason, so
t
andans
are still 5. - The fourth character is '1', and again, nothing changes, so
t
andans
remain 5. - Now, the fifth character is '0'. If we were to split here, the '0' would move to the left substring. This means we add 1 to
t
, makingt = 5 + 1 = 6
. We compare this withans
and sincet
is greater, we updateans
to 6. - Moving to the final character, '1', if we were to split here, we would subtract 1 from
t
because the '1' would move out of the right substring. This gives ust = 6 - 1 = 5
.ans
remains 6 since it was not exceeded.
-
Updating Maximum Score:
- Throughout the process,
ans
is updated to the maximum score encountered during each iteration. The maximum score that we calculated in the example was 6.
- Throughout the process,
-
Return Final Score:
- After the loop, we conclude that the maximum score that can be achieved by splitting the string
s = "011101"
is 6. This is the value stored inans
, which is what our function would return.
- After the loop, we conclude that the maximum score that can be achieved by splitting the string
Solution Implementation
1class Solution:
2 def max_score(self, s: str) -> int:
3 # Initial score considers the first character '0' as +1 and counts '1's in the rest of the string.
4 score = (s[0] == '0') + s[1:].count('1')
5 # Initialized answer with the initial score.
6 max_score = score
7
8 # Loop through the string starting from the second character to the second to last.
9 for i in range(1, len(s) - 1):
10 # If the character is '0', increment score, if '1', decrement it.
11 score += 1 if s[i] == '0' else -1
12 # Update max_score if the current score is greater.
13 max_score = max(max_score, score)
14
15 # Return the maximum score achieved.
16 return max_score
17
1class Solution {
2 public int maxScore(String s) {
3 // Initialize total score for the first partition
4 int totalScore = 0;
5 // If the first character is '0', increase the score by 1
6 if (s.charAt(0) == '0') {
7 totalScore++;
8 }
9 // Calculate initial score for '1's in the string, skipping the first character
10 for (int i = 1; i < s.length(); ++i) {
11 if (s.charAt(i) == '1') {
12 totalScore++;
13 }
14 }
15 // The best score is initially set to the score from the initial partition
16 int maxScore = totalScore;
17
18 // Iterate through the string to find partitions and track the highest score
19 for (int i = 1; i < s.length() - 1; ++i) {
20 // If the current character is '0', increase the total score
21 // If it is '1', decrease the total score
22 totalScore += (s.charAt(i) == '0') ? 1 : -1;
23 // Update the maximum score if the current total score is greater
24 maxScore = Math.max(maxScore, totalScore);
25 }
26 // Return the highest score found amongst all possible partitions
27 return maxScore;
28 }
29}
30
1class Solution {
2public:
3 int maxScore(string s) {
4 // Initialize totalScore to 0. It will represent the total score while traversing the string.
5 int totalScore = 0;
6
7 // If the first character is '0', we increment totalScore as we get one point for it.
8 if (s[0] == '0') {
9 ++totalScore;
10 }
11
12 // Add to totalScore the number of '1' in the string, except for the first character.
13 for (int i = 1; i < s.size(); ++i) {
14 totalScore += s[i] == '1';
15 }
16
17 // Initialize maxScore with the totalScore calculated so far.
18 int maxScore = totalScore;
19
20 // Start traversing the string from the second character to the second-to-last.
21 for (int i = 1; i < s.size() - 1; ++i) {
22 // Increment totalScore if it's a '0', else decrement it for a '1'.
23 totalScore += s[i] == '0' ? 1 : -1;
24
25 // Update maxScore with the higher value between maxScore and totalScore.
26 maxScore = max(maxScore, totalScore);
27 }
28
29 // Return the maximum score found.
30 return maxScore;
31 }
32};
33
1function maxScore(s: string): number {
2 const stringLength = s.length; // Store the length of the input string
3 let maxResult = 0; // Initialize the variable to hold the maximum score
4 let currentScore = 0; // Initialize the variable to hold the current score
5
6 // First, we check if the first character is '0' to possibly increase the current score,
7 // because we are looking for the maximum number of '0's in the left partition
8 // and the maximum number of '1's in the right partition of the string after a split.
9 if (s[0] === '0') {
10 currentScore++;
11 }
12
13 // Calculate the score of 1's in the right partition by iterating over the string
14 // starting at index 1 (second character) because the left partition will have at least
15 // one character.
16 for (let i = 1; i < stringLength; i++) {
17 if (s[i] === '1') {
18 currentScore++;
19 }
20 }
21
22 // Initially set the maximum score to the score calculated above
23 maxResult = Math.max(maxResult, currentScore);
24
25 // Loop through s, starting from the second character to the second-to-last character
26 // since we need to split s into two non-empty partitions.
27 for (let i = 1; i < stringLength - 1; i++) {
28 // If the current character is '0', we add one to the current score
29 // because we are effectively moving a '0' from the right partition (initially the whole string sans the first character)
30 // to the left partition, increasing the left partition's score.
31 if (s[i] === '0') {
32 currentScore++;
33 // If the current character is '1', we subtract one from the current score
34 // because we are moving a '1' from the right partition to the left one,
35 // decreasing the right partition's score.
36 } else if (s[i] === '1') {
37 currentScore--;
38 }
39 // Update the maximum result if the current score is greater
40 maxResult = Math.max(maxResult, currentScore);
41 }
42
43 // Finally return the maximum score found, which corresponds to the
44 // best place to split string s into two partitions
45 return maxResult;
46}
47
Time and Space Complexity
Time Complexity
The time complexity is determined by how many operations the algorithm performs in relation to the input size, which is the length of the string s
in this case.
- First, the algorithm initializes
ans
andt
with the count of '1's in the substrings[1:]
and checks ifs[0]
is '0'. This takesO(n)
time wheren
is the length ofs
, ascount('1')
iterates through the string once. - Then, there's a loop which iterates
n - 2
times (the string length minus 2, as the loop starts at 1 and ends atlen(s) - 1
). Each iteration performs a constant amount of work by checkings[i]
and possibly updatingt
andans
. - Combining both steps, the total number of operations is proportional to
2n - 2
.
Since these are linear operations, the time complexity of the algorithm is O(n)
.
Space Complexity
The space complexity is determined by the amount of extra storage the algorithm uses in relation to the input size.
- The algorithm uses a fixed number of integer variables
ans
,t
, andi
, which use a constant amount of space. - There is no use of any data structure that grows with the input size.
Therefore, the space complexity is O(1)
, as the amount of extra space used does not depend on the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!