diff options
Diffstat (limited to 'longest_repeat_char.c')
-rw-r--r-- | longest_repeat_char.c | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/longest_repeat_char.c b/longest_repeat_char.c new file mode 100644 index 0000000..fe1ad65 --- /dev/null +++ b/longest_repeat_char.c @@ -0,0 +1,32 @@ +// 424. Longest Repeating Character Replacement +#include "leetcode.h" + +/* + * given a string 's' and an integer 'k'. you can choose any character of the + * string and change it to any other uppercase english character. you can + * perform this operation at most 'k' times. return the length of the longest + * substring containing the same letter you can get after performing the above + * operations. + */ + +int characterReplacement(char *s, int k) { + int n = strlen(s), left = 0, right = 0, max_cnt = 0; + int *freq = calloc(26, sizeof(int)); + while (right < n) { + freq[s[right] - 'A']++; + max_cnt = fmax(max_cnt, freq[s[right] - 'A']); + right++; + if (right - left > max_cnt + k) { + freq[s[left] - 'A']--; + left++; + } + } + free(freq); + return right - left; +} + +int main() { + char s1[] = {"ABAB"}, s2[] = {"AABABBA"}; + printf("%d\n", characterReplacement(s1, 2)); // expect: 4 + printf("%d\n", characterReplacement(s2, 1)); // expect: 4 +} |