1332 . palindromic subsequence leetcodeを簡単に削除する

問題声明
文字' s 'と' b 'から成るストリングsを与えられます.つのステップでは、Sから1つのpalindromicサブシーケンスを削除することができます.
指定した文字列を空にするステップ数を返します.
文字列は、与えられた文字列の順序を変更せずに文字を削除することで生成されます.
文字列はパーフォドロームと呼ばれます.

テストケース
例1 :
入力: S = "ababa "
出力: 1
説明:ストリングは、すでにpalindromeです
例2 :
入力:S =「ABB」
出力: 2
説明:「ABB」→「BB」→「」.
palindromicサブシーケンス"a "を"bb "とする.
例3 :
入力: S = "baabb "
出力: 2
説明:"baabb "-"b "->"
palindromic subsequence "baab "と"b "を取り除く.
例4 :
入力:"
出力: 0

考え
主な問題になる前に、サブシーケンスとは何かを理解することができます文字列です.

Subsequence - A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.
For the same example, there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). More generally, we can say that for a sequence of size n, we can have (2^n-1) non-empty sub-sequences in total.
Substring - A subbarray is a contiguous part of array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subbarays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4). In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/subsrings.

それで、現在、我々の問題に来て、我々はストリングを空にして、我々が2つの手紙AとBだけを持っているために、palindromicサブシーケンスを取り除かなければなりません.
1 )与えられた文字列が空であるので、0を返します.
2 )与えられた文字列は既にpalindromeされているので、ステップ= 1になる文字列全体を削除します.したがって、1を返します.
* 3 )与えられた文字列はpalindromeではなく、削除の最初のステップとして' a 'または' b 'を取り除くことを考えます.このステップでは、完全な' a 'を削除し、2番目のステップとして残りの文字' a 'または' b 'を削除します.それで、今度は2を返してください.
そして、これは我々の全体の問題を与えます.

アルゴリズム
1文字列が空ならば真を返します.
2 )左ポインタ= 0を指定します.
3 )右を左にして、次のことを行う
-パラフォニック状態をチェックし、失敗した場合は2を返します.
4 ) 1を返す.

コード

// here there are 3 conditions that we want to consider
// 1. if the string is empty, then return 0. This can be our first check.
// 2. Next one is checking palindrome or not. If the whole string is palindrome, then we can delete it completely. So return 1.
// 3. The next one is either we can remove a completely then b or vice versa. So in this case number of steps will be only 2. 
    // That is first step can be to remove all 'a's and the second step is remove all 'b's.
class Solution {
    public int removePalindromeSub(String s) {
        // string empty
        if (s.length() == 0)
            return 0;
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // palindrome condition
            if (s.charAt(left) == s.charAt(right)) {
                left += 1;
                right -= 1;
            }
            else 
                return 2;
        }
        return 1;
    }
}

時間複雑性:空間複雑性
o ( longthofstring ) o ( 1 )
Github関連:Link