Ubah suai rentetan secara minimum supaya semua subrentetan berbeza

Rentetan ialah jenis objek tertentu yang mewakili jujukan dan aliran aksara data. Rentetan ialah bekas data, sentiasa diwakili dalam format teks. Ia juga digunakan untuk operasi konseptual, perbandingan, belah, gabungkan, ganti, potong, panjang, dalaman, kesamaan, perbandingan dan subrentetan. substring() ialah proses penapisan data yang mengekstrak data antara data yang disimpan dari awal hingga akhir. substring() tidak mengubah rentetan asal. Dalam set data, apabila kita mempunyai aksara yang berbeza, ia boleh diwakili sebagai elemen data yang berbeza. Contohnya: 'a' dan 'r' adalah berbeza, manakala 'r' dan 'r' adalah sama. Jadi, rentetan katakan, oren mengandungi 6 aksara yang berbeza. Begitu juga, epal rentetan mengandungi hanya 4 aksara yang berbeza.

Andaikan, "s" ialah rentetan, dan kita perlu mencari bilangan minimum perubahan yang diperlukan untuk semua subrentetan untuk menjadikan rentetan itu berbeza.

• Panjang tali - 26

• Input yang diberikan − T ialah kes ujian bagi baris pertama, iaitu integer. Untuk setiap kes ujian, hanya akan ada satu baris yang mengandungi 26 aksara.

• Output - Kami akan mendapat bilangan perubahan minimum untuk setiap kes ujian.

• Kekangan aliran kaedah logik

  • 1

  • 1

Dalam artikel hari ini, kita akan belajar cara mengubah suai rentetan supaya semua subrentetan berbeza.

Algoritma untuk membuat subrentetan berbeza

Ini adalah algoritma yang mungkin untuk beroperasi pada rentetan supaya semua subrentetan adalah berbeza sambil meminimumkan perubahan.

Langkah pertama - mulakan.
Langkah 2 − Gunakan dua gelung bersarang untuk menjana subrentetan.
Langkah 3 - Gelung luar bermula dari i = 0 dan tolak panjang rentetan dengan 1.
Langkah 4 - Gelung dalam bermula dari j = 0 dan tolak panjang rentetan dengan 1.
Langkah 5 − Bina pembolehubah kiraan menggunakan nilai sifar.
Langkah 6− Di dalam gelung luar, cipta pembolehubah_ciri yang tersendiri.
Langkah 7 - Buat tatasusunan frekuensi.
Langkah 8− Tetapkan semua elemen sifar.
Langkah 9 - Semak sama ada kekerapan rentetan[j] - 'a' ialah sifar.
Langkah 10− Jika sifar, tambahkan 1.
Langkah 11− Jika tidak, pecahkannya menjadi gelung dalam.
Langkah 12 - Jika kiraan lebih besar daripada sifar, kembalikan kiraan.
Langkah 13 - Jika tidak, kembalikan -1.
Langkah 14 - Penamatan.
Sintaks untuk mencipta semua subrentetan berbeza

string.substring(start, end)

Dalam sintaks ini kita dapat melihat cara membuat perubahan minimum pada rentetan supaya semua subrentetan adalah berbeza.

Parameter
Mula - Kedudukan permulaan perlu diisytiharkan. Indeks aksara pertama di sini ialah 0.
Tamat − Ia adalah proses pilihan yang terletak di hujung (termasuk tetapi tidak terhad kepada).

Kaedah

Kaedah 1− Cari bilangan minimum perubahan yang menjadikan semua subrentetan rentetan berbeza.

Cari bilangan minimum perubahan supaya semua subrentetan rentetan menjadi berbeza

Dalam kaedah ini, kita akan belajar cara membuat semua subrentetan berbeza. Di sini, setiap watak mesti berbeza. Kita hanya perlu mencari bilangan aksara. Jika panjang rentetan lebih daripada 26, maka kita hanya perlu menukarnya kepada rentetan. Di sini kita akan menulis logik yang sama di tempat yang berbeza.

Contoh 1: Menggunakan C++

#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int minChanges(string &str) {
   int n = str.length();
   if (n > MAX_CHAR)
   return -1;
   int dist_count = 0;
   int count[MAX_CHAR] = {0};
   for (int i = 0; i < n; i++) {
      if (count[str[i] - 'a'] == 0)
      dist_count++;
      count[(str[i] - 'a')]++;
   }
   return (n - dist_count);
}
int main() {
   string str = "aebaecedabbeedee";
   cout << minChanges(str);
   return 0;
}

Output

11

Contoh 2: Dengan menggunakan Java

import java.lang.*;
import java.util.*;
public class tutorialspoint {
   static final int MAX_CHAR = 26;
   public static int minChanges(String str) {
      int n = str.length();
      if (n > MAX_CHAR)
      return -1;
      int dist_count = 0;
      int count[] = new int[MAX_CHAR];
      for(int i = 0; i < MAX_CHAR; i++)
      count[i] = 0;
      for (int i = 0; i < n; i++) {
         if(count[str.charAt(i)-'a'] == 0)
         dist_count++;
         count[str.charAt(i)-'a']++;
      }
      return (n-dist_count);
   }
   public static void main (String[] args) {
      String str = "aebaecedabbeedee";
      System.out.println(minChanges(str));
   }
}

Output

11

Contoh 1: Menggunakan Python

MAX_CHAR = [26]
def minChanges(str):

	n = len(str )
	if (n > MAX_CHAR[0]):
		return -1
	dist_count = 0
	count = [0] * MAX_CHAR[0]

	for i in range(n):
		if (count[ord(str[i]) - ord('a')] == 0) :
			dist_count += 1
		count[(ord(str[i]) - ord('a'))] += 1
	return (n - dist_count)
if __name__ == '__main__':
	str = "aebaecedabbeedee"
	print(minChanges(str))
	

Output

11

Kesimpulan

Hari ini, dalam artikel ini, kami belajar cara membuat semua subrentetan berbeza dengan perubahan yang minimum. Di sini kami telah mencipta beberapa kod yang mungkin dengan mengikuti algoritma yang diterangkan dalam C++, Java dan Python. Semoga ini membantu anda memperoleh pemahaman yang lebih menyeluruh tentang subjek tersebut.

Atas ialah kandungan terperinci Ubah suai rentetan secara minimum supaya semua subrentetan berbeza. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!