[HackerRank]交替的字元(Alternating Characters)

題目描述

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

原題網址

https://www.hackerrank.com/challenges/alternating-characters

輸入格式

輸入有兩行。第一行是一個整數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的時候,由於和前一個字元重複了,所以重複次數要加一。掃描結束後,由於重複次數即為要刪除的字元數量,所以將其直接輸出。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章