題目描述

給定一個由字元A和B組成的字串,請找出最少要刪除多少個字元才能使這個字串的字元不連續。



原題網址

輸入格式

輸入有兩行。第一行是一個整數T,表示有幾組要計算的字串,範圍在1到10之間(包含1和10)。接下來的T行,每行都是一組字串,長度在1到105之間(包含1和105)。

輸出格式

輸出有T行,每行都是各組字串最少需要刪除的字元數量。

範例輸入

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

範例輸出

3
4
0
0
4

額外解釋

第一組,AAAA,要把3個A刪除。

第二組,BBBBB,要把4個B刪除。

第三組,ABABABAB,不需刪除任何字元。

第四組,BABABA,不需刪除任何字元。

第五組,AAABBB,需刪除2個A和2個B。

解題概念

為了要計算最少需要刪除的字元數量才能使字串中的字元不重複,可以先宣告兩個變數來記錄重複次數和重複的字元,接著利用迴圈從頭到尾掃描一次要被計算的字串。如果遇到重複的字元,就把記錄重複次數的變數加一。舉例來說,字串「aab」,當掃描到在索引1的第二個a的時候,由於和前一個字元重複了,所以重複次數要加一。掃描結束後,由於重複次數即為要刪除的字元數量,所以將其直接輸出。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);

        int T = Integer.parseInt(sc.nextLine());
        while (T-- > 0) {
            final char[] s = sc.nextLine().toCharArray();
            int sum = 0;
            char cc = '\0';
            for (final char c : s) {
                switch (cc) {
                    case '\0':
                        cc = c;
                        break;
                    default:
                        if (cc == c) {
                            ++sum;
                        } else {
                            cc = c;
                        }
                }
            }
            System.out.println(sum);
        }
    }
}