1332. Remove Palindromic Subsequences

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

 

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either 'a' or 'b'.

Rust Solution

struct Solution;

trait Palindrome {
    fn is_palindrome(&self) -> bool;
}

impl Palindrome for String {
    fn is_palindrome(&self) -> bool {
        let mut i = 0;
        let n = self.len();
        let mut j = n - 1;
        let v: Vec<char> = self.chars().collect();
        while i <= j {
            if v[i] != v[j] {
                return false;
            }
            i += 1;
            j -= 1;
        }
        true
    }
}

impl Solution {
    fn remove_palindrome_sub(s: String) -> i32 {
        if s.is_empty() {
            0
        } else {
            if s.is_palindrome() {
                1
            } else {
                2
            }
        }
    }
}

#[test]
fn test() {
    let s = "ababa".to_string();
    let res = 1;
    assert_eq!(Solution::remove_palindrome_sub(s), res);
    let s = "abb".to_string();
    let res = 2;
    assert_eq!(Solution::remove_palindrome_sub(s), res);
    let s = "baabb".to_string();
    let res = 2;
    assert_eq!(Solution::remove_palindrome_sub(s), res);
    let s = "".to_string();
    let res = 0;
    assert_eq!(Solution::remove_palindrome_sub(s), res);
}

Having problems with this solution? Click here to submit an issue on github.