Question

1750. Minimum Length of String After Deleting Similar Ends

中文文档

Description

Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:

1. Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
2. Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
3. The prefix and the suffix should not intersect at any index.
4. The characters from the prefix and suffix must be the same.
5. Delete both the prefix and the suffix.

Return _the minimum length of _s _after performing the above operation any number of times (possibly zero times)_.

 

Example 1:

Input: s = "ca"
Output: 2
Explanation: You can't remove any characters, so the string stays as is.

Example 2:

Input: s = "cabaabac"
Output: 0
Explanation: An optimal sequence of operations is:
- Take prefix = "c" and suffix = "c" and remove them, s = "abaaba".
- Take prefix = "a" and suffix = "a" and remove them, s = "baab".
- Take prefix = "b" and suffix = "b" and remove them, s = "aa".
- Take prefix = "a" and suffix = "a" and remove them, s = "".

Example 3:

Input: s = "aabccabba"
Output: 3
Explanation: An optimal sequence of operations is:
- Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
- Take prefix = "b" and suffix = "bb" and remove them, s = "cca".

 

Constraints:

• 1 <= s.length <= 105
• s only consists of characters 'a', 'b', and 'c'.

Solutions

Solution 1: Two pointers

We define two pointers $i$ and $j$ to point to the head and tail of the string $s$ respectively, then move them to the middle until the characters pointed to by $i$ and $j$ are not equal, then $\max(0, j - i + 1)$ is the answer.

The time complexity is $O(n)$ and the space complexity is $O(1)$. Where $n$ is the length of the string $s$.

class Solution:
  def minimumLength(self, s: str) -> int:
    i, j = 0, len(s) - 1
    while i < j and s[i] == s[j]:
      while i + 1 < j and s[i] == s[i + 1]:
        i += 1
      while i < j - 1 and s[j - 1] == s[j]:
        j -= 1
      i, j = i + 1, j - 1
    return max(0, j - i + 1)

class Solution {
  public int minimumLength(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
      while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {
        ++i;
      }
      while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {
        --j;
      }
      ++i;
      --j;
    }
    return Math.max(0, j - i + 1);
  }
}

class Solution {
public:
  int minimumLength(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j && s[i] == s[j]) {
      while (i + 1 < j && s[i] == s[i + 1]) {
        ++i;
      }
      while (i < j - 1 && s[j] == s[j - 1]) {
        --j;
      }
      ++i;
      --j;
    }
    return max(0, j - i + 1);
  }
};

func minimumLength(s string) int {
  i, j := 0, len(s)-1
  for i < j && s[i] == s[j] {
    for i+1 < j && s[i] == s[i+1] {
      i++
    }
    for i < j-1 && s[j] == s[j-1] {
      j--
    }
    i, j = i+1, j-1
  }
  return max(0, j-i+1)
}

function minimumLength(s: string): number {
  let i = 0;
  let j = s.length - 1;
  while (i < j && s[i] === s[j]) {
    while (i + 1 < j && s[i + 1] === s[i]) {
      ++i;
    }
    while (i < j - 1 && s[j - 1] === s[j]) {
      --j;
    }
    ++i;
    --j;
  }
  return Math.max(0, j - i + 1);
}

impl Solution {
  pub fn minimum_length(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let mut start = 0;
    let mut end = n - 1;
    while start < end && s[start] == s[end] {
      while start + 1 < end && s[start] == s[start + 1] {
        start += 1;
      }
      while start < end - 1 && s[end] == s[end - 1] {
        end -= 1;
      }
      start += 1;
      end -= 1;
    }
    (0).max(end - start + 1) as i32
  }
}

int minimumLength(char* s) {
  int n = strlen(s);
  int start = 0;
  int end = n - 1;
  while (start < end && s[start] == s[end]) {
    while (start + 1 < end && s[start] == s[start + 1]) {
      start++;
    }
    while (start < end - 1 && s[end] == s[end - 1]) {
      end--;
    }
    start++;
    end--;
  }
  if (start > end) {
    return 0;
  }
  return end - start + 1;
}