diff options
Diffstat (limited to 'max_score_split_str.c')
-rw-r--r-- | max_score_split_str.c | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/max_score_split_str.c b/max_score_split_str.c new file mode 100644 index 0000000..f636fce --- /dev/null +++ b/max_score_split_str.c @@ -0,0 +1,31 @@ +// 1422. Maximum Score After Splitting a String +#include "leetcode.h" + +/* + * given a string 's' of zeros and ones, return the maximum score after + * splitting the string into two non-empty substrings (ie. left and right). the + * score after splitting a string is the number of zeros in the left substring + * plus the number of ones in the right substring. + */ + +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 main() { + char *s1 = "011101", *s2 = "00111", *s3 = "1111"; + printf("%d\n", maxScore(s1)); // expect: 5 + printf("%d\n", maxScore(s2)); // expect: 5 + printf("%d\n", maxScore(s3)); // expect: 3 +} |