Problem Description
Explanation:
To solve this problem, we can use a greedy approach. We repeatedly remove "ab" and "ba" substrings from the given string until no more such substrings can be removed. During each removal, we keep track of the points gained and return the maximum score.
- Initialize a variable
scoreto 0. - While there are "ab" or "ba" substrings in the string:
- Find the index of the first occurrence of "ab" or "ba".
- Remove the found substring and add x or y points to the score accordingly.
- Return the final score.
Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1)
:
Solutions
class Solution {
public int maximumGain(String s, int x, int y) {
StringBuilder sb = new StringBuilder(s);
int score = 0;
while (true) {
int idx1 = sb.indexOf("ab");
int idx2 = sb.indexOf("ba");
if (idx1 == -1 && idx2 == -1) {
break;
}
if (idx1 != -1 && (idx2 == -1 || idx1 < idx2)) {
sb.delete(idx1, idx1 + 2);
score += x;
} else {
sb.delete(idx2, idx2 + 2);
score += y;
}
}
return score;
}
}Loading editor...