Ubah suai rentetan dengan memasukkan aksara supaya setiap subrentetan panjang K mengandungi aksara unik sahaja

Apabila memproses rentetan, tugas biasa ialah memastikan rentetan itu memenuhi syarat tertentu. Salah satu syaratnya adalah untuk memastikan bahawa setiap subrentetan panjang K dalam rentetan hanya mengandungi aksara unik. Ini adalah keperluan biasa dalam isu yang berkaitan dengan pengekodan data, manipulasi rentetan dan kriptografi.

Pernyataan Masalah

Masalah yang kami cuba selesaikan boleh dinyatakan seperti berikut -

Diberi rentetan str dan integer K, ubah suai rentetan dengan memasukkan aksara supaya setiap subrentetan panjang K dalam rentetan hanya mengandungi aksara unik.

Cadangan penyelesaian

Kita boleh menyelesaikan masalah ini dengan menggunakan teknik tetingkap gelongsor, iaitu kaedah untuk memeriksa sifat subarray atau subrentetan berturut-turut dengan cekap dalam tatasusunan atau rentetan yang lebih besar.

Mari kami terangkan langkah-langkah algoritma ini secara terperinci -

• Mulakan unordered_map kosong (peta cincang) untuk menjejaki kekerapan aksara dalam subrentetan semasa.

• Lelaran ke atas aksara dalam rentetan menggunakan tetingkap gelongsor bersaiz K.

• Jika aksara sudah ada dalam peta cincang, masukkan aksara baharu sehingga aksara unik diperoleh atau saiz tetingkap gelongsor ialah K.

• Alihkan tetingkap gelongsor satu aksara dan ulangi proses sehingga anda mencapai penghujung rentetan.

Kerumitan masa algoritma ini ialah O(n), dengan n ialah panjang rentetan. Ini kerana kami mengulangi setiap aksara dalam rentetan sekali sahaja.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Mari kita lihat kod C++ yang melaksanakan algoritma di atas -

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

string modifyString(string str, int K) {
   int n = str.size();
   string result = "";
   for(int i = 0; i < n; i++) {
      unordered_map<char, int> freq;
      int j = i;
      while(j < n && j < i + K) {
         while(j < n && freq[str[j]]) {
               result += 'a' + (rand() % 26); // insert a random character
         }
         freq[str[j++]]++;
         result += str[j];
      }
      i = j - 1;
   }
   return result;
}

int main() {
   string str = "abcabc";
   int K = 3;
   cout << modifyString(str, K) << endl;
   return 0;
}

Output

bcabc

Kod ini akan memasukkan huruf Inggeris huruf kecil secara rawak apabila ia menemui aksara berulang.

Contoh kes ujian

Mari kita ambil contoh untuk memahami isu ini dengan lebih baik.

Pertimbangkan rentetan str = "abcabc" dan K = 3.

Selepas menjalankan kod, anda mungkin mendapat hasil yang serupa dengan abcxyzabc. Subrentetan tiga aksara ialah abc, bcx, cxy, xyz, yza, zab, abc, yang kesemuanya mengandungi aksara unik.

NOTA− Keputusan mungkin berbeza kerana kami memasukkan aksara rawak.

Kesimpulan

Ringkasnya, algoritma ini menyediakan cara untuk mengubah suai rentetan untuk memastikan setiap subrentetan panjang K mempunyai aksara yang unik. Ini adalah penyelesaian cekap yang memanfaatkan kuasa teknologi tingkap gelongsor dan fleksibiliti C++. Kami menggalakkan anda untuk bereksperimen dengan rentetan yang berbeza dan nilai K untuk memahami sepenuhnya konsep ini.

Atas ialah kandungan terperinci Ubah suai rentetan dengan memasukkan aksara supaya setiap subrentetan panjang K mengandungi aksara unik sahaja. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!