diff options
author | Jack Sangdahl <[email protected]> | 2025-01-01 01:12:44 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-01 01:12:44 +0100 |
commit | 3fcaa644e9bc20851329227b01d496ab1318ca18 (patch) | |
tree | f2423defee5d0bed45165b8f5426e36335784d9c | |
parent | aeac76f37b44fe79a23411fcd6e3e8ea79a2b5df (diff) | |
download | leetcode-3fcaa644e9bc20851329227b01d496ab1318ca18.tar.gz leetcode-3fcaa644e9bc20851329227b01d496ab1318ca18.zip |
1422. maximum score after splitting a string
-rw-r--r-- | max_score_split_str.c | 25 | ||||
-rw-r--r-- | max_score_split_str.py | 14 |
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__": |