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'.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=1000) :: s
    integer :: nsteps

    call get_command_argument(1, s)

    nsteps = solve(s)

    write (*, '(I0)') nsteps

contains

    function solve(s) result(nsteps)
        implicit none
        character(len=*), intent(in) :: s
        integer :: nsteps
        integer :: i, j

        do while (any(s /= ''))
            i = 1
            j = len(s)
            do while (i < j)
                if (s(i:j) == s(i:j)(::-1)) then
                    s(i:j) = ''
                    exit
                end if
                i = i + 1
            end do
        end do

        nsteps = len(trim(s))
    end function solve
end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, l, m, n, steps
character(len=1000) :: s

! Read input
read(*,*) s

! Initialize variables
steps = 0

! Loop until the string is empty
do while (s /= "")
    ! Find the first palindromic subsequence
    i = 1
    do while (i <= len(s))
        ! Check if the substring is palindromic
        j = i
        k = len(s)
        do while (j < k)
            if (s(j:j) /= s(k:k)) exit
            j = j + 1
            k = k - 1
        end do

        ! If the substring is palindromic, remove it
        if (j == k) then
            s(i:k) = ""
            steps = steps + 1
            exit
        end if

        ! Increment i
        i = i + 1
    end do
end do

! Print output
write(*,*) steps

end
🌐 Data from online sources 
def countStrings(n):
    mod = 10**9 + 7
    a, b = 1, 1
    for _ in range(n):
        a = (a * 2) % mod
        b = (b * 3) % mod
    return (b - a + mod) % mod

The problem requires us to find the total number of valid strings of the given length based on certain rules. To solve this, we calculate:
  1. a: Count of all strings of length n using just 'a'. Each position can be either 'a' or not 'a', so there are 2 possibilities for each position. Therefore, the count is 2^n.
  2. b: Count of all strings of length n using only 'a' and 'b'. Any position can be either 'a', 'b', or neither 'a' nor 'b', so there are 3 possibilities for each position. Therefore, the count is 3^n.

As we have already counted the strings with all positions either 'a' or not 'a' in step one, we need to subtract these duplicates. Thus, the answer is the difference (b - a) plus the modulo value to make it positive, and the final result is calculated using % mod.

🌐 Data from online sources 
int countStrings(int n) {
    const int mod = 1e9 + 7;
    long long a = 1, b = 1;
    for (int i = 0; i < n; ++i) {
        a = (a * 2) % mod;
        b = (b * 3) % mod;
    }
    return (b - a + mod) % mod;
}

The problem requires us to find the total number of valid strings of the given length based on certain rules. To solve this, we calculate:
  1. a: Count of all strings of length n using just 'a'. Each position can be either 'a' or not 'a', so there are 2 possibilities for each position. Therefore, the count is 2^n.
  2. b: Count of all strings of length n using only 'a' and 'b'. Any position can be either 'a', 'b', or neither 'a' nor 'b', so there are 3 possibilities for each position. Therefore, the count is 3^n.

As we have already counted the strings with all positions either 'a' or not 'a' in step one, we need to subtract these duplicates. Thus, the answer is the difference (b - a) plus the modulo value to make it positive, and the final result is calculated using % mod.