題目描述
給定一個由字元A和B組成的字串,請找出最少要刪除多少個字元才能使這個字串的字元不連續。
原題網址
輸入格式
輸入有兩行。第一行是一個整數T,表示有幾組要計算的字串,範圍在1到10之間(包含1和10)。接下來的T行,每行都是一組字串,長度在1到105之間(包含1和105)。
輸出格式
輸出有T行,每行都是各組字串最少需要刪除的字元數量。
範例輸入
5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB
AAAA
BBBBB
ABABABAB
BABABA
AAABBB
範例輸出
3
4
0
0
4
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);
}
}
}