1332-RemovePalindromicSubsequences.go

package main

// 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'.

import "fmt"

// 双指针
func removePalindromeSub(s string) int {
    if len(s) == 0 { 
        return 0 
    }
    l, r := 0, len(s) - 1
    for l < r {
        if s[l] == s[r] {
            l++
            r--
        } else {
            break
        }
    }
    if l == r || l > r { // 需要删一个
        return 1 
    }
    return 2 // worst case is 2
}

func main() {
    // Example 1:
    // Input: s = "ababa"
    // Output: 1
    // Explanation: s is already a palindrome, so its entirety can be removed in a single step.
    fmt.Println(removePalindromeSub("ababa")) // 1
    // Example 2:
    // Input: s = "abb"
    // Output: 2
    // Explanation: "abb" -> "bb" -> "". 
    // Remove palindromic subsequence "a" then "bb".
    fmt.Println(removePalindromeSub("abb")) // 2
    // Example 3:
    // Input: s = "baabb"
    // Output: 2
    // Explanation: "baabb" -> "b" -> "". 
    // Remove palindromic subsequence "baab" then "b".
    fmt.Println(removePalindromeSub("baabb")) // 2
}