Kira bilangan subrentetan yang terdiri daripada satu aksara yang berbeza

Dalam artikel ini, kita akan membincangkan masalah mengira bilangan subrentetan yang terdiri daripada aksara tunggal yang berbeza dalam rentetan tertentu. Kami akan meneroka algoritma yang cekap untuk menyelesaikan masalah ini dan menyediakan kod C++ untuk melaksanakannya.

Pernyataan Masalah

Diberi rentetan S, tugasnya ialah mengira bilangan subrentetan yang terdiri daripada aksara tunggal yang berbeza.

Sebagai contoh, jika rentetan input ialah "aaaaa", output hendaklah 15 kerana terdapat 15 subrentetan yang terdiri daripada aksara tunggal yang berbeza. Subrentetan ialah "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "aaa ” , “aaa”, “aaaa”, “aaaa”, “aaaa”.

Algoritma

Kami boleh menyelesaikan masalah ini dengan kerumitan masa linear. Kita boleh mengulangi rentetan input dan menjejaki aksara semasa dan panjang subrentetan semasa. Setiap kali aksara baharu ditemui atau penghujung rentetan dicapai, kita boleh mengira bilangan subrentetan yang boleh dibentuk oleh aksara semasa dan panjang subrentetan semasa.

Berikut adalah algoritma langkah demi langkah untuk menyelesaikan masalah ini -

• Mulakan kiraan dan lenkan kepada 1.

• Lelaran pada rentetan S daripada indeks 1 hingga n-1.

• Jika watak semasa sama dengan watak sebelumnya, len dinaikkan sebanyak 1.

• Jika aksara semasa berbeza daripada aksara sebelumnya, tambah (len*(len+1))/2 untuk mengira dan tetapkan semula len ​​ke 1.

• Kiraan pulangan.

Mari kita ambil rentetan "aaaaa" sebagai contoh untuk memahami algoritma -

• Mulakan kiraan dan lenkan kepada 1.

• Lelaran pada rentetan daripada indeks 1 hingga n-1:

• Pada indeks 1, watak semasa adalah sama dengan watak sebelumnya, jadi len dinaikkan sebanyak 1.

• Pada indeks 2, watak semasa adalah sama dengan watak sebelumnya, jadi len dinaikkan sebanyak 1.

• Pada indeks 3, watak semasa adalah sama dengan watak sebelumnya, jadi len dinaikkan sebanyak 1.

• Pada indeks 4, watak semasa adalah sama dengan watak sebelumnya, jadi len dinaikkan sebanyak 1.

• Kita telah sampai ke penghujung rentetan, jadi tambah (len*(len+1))/2 untuk mengira. Kira = Kira + (5*(5+1))/2 = 15.

• Kiraan pulangan.

Pelaksanaan C++

Ini ialah kod C++ yang melaksanakan algoritma di atas -

Contoh

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

int countSubstrings(string S) {
   int n = S.length();
   int count = 1, len = 1;
   for (int i = 1; i < n; i++) {
      if (S[i] == S[i-1]) {
         len++;
      } else {
         count += (len*(len+1))/2;
         len = 1;
      }
   }
   count += (len*(len+1))/2;
   return count-1;
}

int main() {
   string S = "aaaaa";
   int count = countSubstrings(S);
   cout << count << endl;
   return 0;
}

Output

15

Kesimpulan

Dalam artikel ini, kami membincangkan masalah mengira bilangan subrentetan yang terdiri daripada aksara tunggal yang berbeza dalam rentetan tertentu. Kami menyediakan algoritma yang cekap untuk menyelesaikan masalah ini dalam kerumitan masa linear dan melaksanakannya dalam C++. Masalah ini juga boleh diselesaikan menggunakan teknik lain, tetapi algoritma di atas menyediakan

Atas ialah kandungan terperinci Kira bilangan subrentetan yang terdiri daripada satu aksara yang berbeza. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!