โปรแกรม C++ เพื่อค้นหาสตริงที่มีสตริงย่อย palindrome ที่มีความยาวไม่เกิน k

สมมติว่าเรามีตัวเลขสองตัว n และ k ให้เรากำลังพยายามสร้างสตริง S ที่มีอักขระเพียงสามประเภท 'a', 'b' และ 'c' ความยาวสูงสุดของสตริงย่อยของสตริง S ที่เป็นพาลินโดรมซึ่งไม่เกิน k

ดังนั้นหากอินพุตเป็นเหมือน n =3; k =2 ผลลัพธ์จะเป็น "aab" เนื่องจากมีความยาว 3 และสตริงย่อย palindrome คือ "aa" โดยมีความยาวอย่างน้อย 2 (คำตอบอื่น ๆ ก็เป็นไปได้เช่นกัน)

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

S := a blank string
j := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   S := S concatenate (j + ASCII of 'a') as character
   j := (j + 1) mod 3
return S

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;

string solve(int n, int k) {
   string S = "";
   int j = 0;
   for (int i = 0; i < n; i++) {
      S += j + 'a';
      j = (j + 1) % 3;
   }
   return S;
}
int main() {
   int n = 3;
   int k = 2;
   cout << solve(n, k) << endl;
}

อินพุต

3, 2

ผลลัพธ์

abc