c462 - apcs 交錯字串 (Alternating Strings)

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出輸入字串中最長 k-交錯字串的長度。k-交錯字串指的是，子字串中每 k 個字元，其大小寫狀態必須交替。例如，k=2 時，如果第一個字元是小寫，則接下來的 k-1 個字元必須是大小寫交替。

解題思路

程式碼使用貪心法來尋找最長交錯字串。它遍歷字串，並嘗試從每個位置開始找到一個 k-交錯字串。對於每個位置，它檢查從該位置開始的 k 個字元是否滿足交替條件。如果滿足，則繼續檢查下一個 k 個字元，直到交替條件不再滿足。在遍歷過程中，記錄找到的最長交錯字串的長度。

程式首先將字串中的每個字元標記為 0 (大寫) 或 1 (小寫)。然後，它使用一個迴圈來遍歷字串，並嘗試從每個位置開始找到一個 k-交錯字串。在迴圈內部，它使用一個 while 迴圈來檢查從當前位置開始的 k 個字元是否滿足交替條件。如果滿足，則將交錯字串的長度增加 k，並更新最長交錯字串的長度。如果交替條件不再滿足，則跳出 while 迴圈，並移動到下一個位置。

複雜度分析

• 時間複雜度: O(n*k)，其中 n 是字串的長度，k 是交錯間隔。最壞情況下，需要遍歷整個字串，並且對於每個位置，可能需要檢查 k 個字元。
• 空間複雜度: O(n)，用於儲存字串中每個字元的大小寫標記。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	int k,ans=0;
	string a;
	cin >> k;
	cin >> a;
	int al=a.length();
	bool n[al];
	for(int i=0;i<al;++i)
		(a[i]>='a')?n[i]=0:n[i]=1;
	for(int i=0,rem=0;i+k<al;){
		int lcs=0;
		bool chat=n[i];
		rem=i;
		while(n[i]==chat&&i+k<al){
			for(int j=0;j<k;++j){
				if(n[i+j]!=chat){
					chat=n[i+j];
					break;
				}
			}
			if(chat==n[i]){
				chat=!chat;
				lcs+=k;
				if(lcs>ans)
					ans=lcs;
				i+=k;
			}
			else
				break;
		}
		i=rem+1;
	}
	if(k==1&&al==1)ans=1;
	cout << ans << "\n";
}