aboutsummaryrefslogtreecommitdiff
path: root/min_len_str_del_end.c
blob: d19c78228b8b90058a93a77b6c692e5e46b64428 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 1750. Minimum Length of String After Deleting Similar Ends
#include "leetcode.h"

/*
 * given a string 's' consisting of only characters a, b, and c you are asked to
 * apply the following algorithm on the string any number of times. first, pick
 * a non-empty prefix from the string 's' where all the characters in the prefix
 * are equal. next, pick a non-empty suffix from the string 's' where all the
 * characters in the suffix are equal. the prefix and the suffix should not
 * intersect at any index. the characters from the prefix and the suffix must be
 * the same. delete both the prefix and the suffix. return the minimum length of
 * 's' after performining the above operation any number of times.
 */

int minimumLength(char *s) {
  int n = strlen(s);
  int left = 0, right = n - 1;
  while (left < n && right > left && s[left] == s[right]) {
    char c = s[left];
    while (s[left] == c)
      left++;
    while (right > left && s[right] == c)
      right--;
  }
  return right - left + 1;
}

int main() {
  char *s1 = "ca", *s2 = "cabaabac", *s3 = "aabccabba";
  printf("%d\n", minimumLength(s1)); // expect: 2
  printf("%d\n", minimumLength(s2)); // expect: 0
  printf("%d\n", minimumLength(s3)); // expect: 3
}