aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-01 01:12:44 +0100
committerJack Sangdahl <[email protected]>2025-01-01 01:12:44 +0100
commit3fcaa644e9bc20851329227b01d496ab1318ca18 (patch)
treef2423defee5d0bed45165b8f5426e36335784d9c
parentaeac76f37b44fe79a23411fcd6e3e8ea79a2b5df (diff)
downloadleetcode-3fcaa644e9bc20851329227b01d496ab1318ca18.tar.gz
leetcode-3fcaa644e9bc20851329227b01d496ab1318ca18.zip
1422. maximum score after splitting a string
-rw-r--r--max_score_split_str.c25
-rw-r--r--max_score_split_str.py14
2 files changed, 20 insertions, 19 deletions
diff --git a/max_score_split_str.c b/max_score_split_str.c
index f636fce..533cab0 100644
--- a/max_score_split_str.c
+++ b/max_score_split_str.c
@@ -9,18 +9,19 @@
*/
int maxScore(char *s) {
- int n = strlen(s), ans = 0;
- int *suffix_one = malloc(n * sizeof(int));
- int *prefix_zero = malloc(n * sizeof(int));
- suffix_one[n - 1] = (s[n - 1] == '1');
- for (int i = n - 2; i >= 0; i--)
- suffix_one[i] = suffix_one[i + 1] + (s[i] == '1');
- prefix_zero[0] = (s[0] == '0');
- for (int i = 1; i < n; i++)
- prefix_zero[i] = prefix_zero[i - 1] + (s[i] == '0');
- for (int i = 1; i < n; i++)
- ans = fmax(ans, suffix_one[i] + prefix_zero[i - 1]);
- return ans;
+ int ones = 0, tmp = s[0] == '0' ? 1 : 0, score = tmp;
+ for (int i = 1; i < strlen(s) - 1; ++i) {
+ if (s[i] == '0')
+ tmp++;
+ else {
+ ones++;
+ tmp--;
+ }
+ if (tmp > score)
+ score = tmp;
+ }
+ ones += s[strlen(s) - 1] == '1' ? 1 : 0;
+ return ones + score;
}
int main() {
diff --git a/max_score_split_str.py b/max_score_split_str.py
index 5152d8a..7cde5e7 100644
--- a/max_score_split_str.py
+++ b/max_score_split_str.py
@@ -14,14 +14,14 @@ class Solution(object):
:type s: str
:rtype: int
"""
- max_score = prefix_zero = 0
- suffix_one = s.count("1")
+ ans, zeros, ones = 0, 0, s.count("1")
for i in range(len(s) - 1):
- prefix_zero += s[i] == "0"
- suffix_one -= s[i] == "1"
- max_score = max(max_score, prefix_zero + suffix_one)
-
- return max_score
+ if s[i] == "1":
+ ones -= 1
+ else:
+ zeros += 1
+ ans = max(ans, zeros + ones)
+ return ans
if __name__ == "__main__":