Ändern Sie eine Zeichenfolge minimal, sodass alle Teilzeichenfolgen unterschiedlich sind

Eine Zeichenfolge ist ein bestimmter Objekttyp, der die Reihenfolge und den Fluss von Datenzeichen darstellt. Eine Zeichenfolge ist ein Datencontainer, der immer im Textformat dargestellt wird. Es wird auch für konzeptionelle, Vergleichs-, Teilungs-, Verbindungs-, Ersetzungs-, Trimm-, Längen-, Internalisierungs-, Gleichheits-, Vergleichs- und Teilzeichenfolgenoperationen verwendet. substring() ist ein Datenverfeinerungsprozess, der Daten zwischen gespeicherten Daten vom Anfang bis zum Ende extrahiert. substring() ändert die ursprüngliche Zeichenfolge nicht. Wenn wir in einem Datensatz unterschiedliche Zeichen haben, können diese als unterschiedliche Datenelemente dargestellt werden. Beispiel: „a“ und „r“ sind unterschiedlich, während „r“ und „r“ gleich sind. Eine Zeichenfolge von beispielsweise Orange enthält also 6 verschiedene Zeichen. Ebenso enthält die Zeichenfolge apple nur 4 unterschiedliche Zeichen.

Angenommen, „s“ ist eine Zeichenfolge und wir müssen die Mindestanzahl an Änderungen ermitteln, die für alle Teilzeichenfolgen erforderlich sind, um die Zeichenfolge unterschiedlich zu machen.

• Länge der Schnur – 26

• Die gegebene Eingabe − T ist der Testfall der ersten Zeile, die eine ganze Zahl ist. Für jeden Testfall gibt es nur eine Zeile mit 26 Zeichen.

• Ausgabe – Wir erhalten die Mindestanzahl an Änderungen für jeden Testfall.

• Einschränkungen des logischen Methodenablaufs

  • 1

  • 1

Im heutigen Artikel erfahren wir, wie man einen String so ändert, dass alle Teilstrings unterschiedlich sind.

Algorithmus zum Unterscheiden von Teilzeichenfolgen

Dies ist ein möglicher Algorithmus zum Bearbeiten einer Zeichenfolge, sodass alle Teilzeichenfolgen eindeutig sind und gleichzeitig Änderungen minimiert werden.

• Schritt eins – starten.

• Schritt 2 – Verwenden Sie zwei verschachtelte Schleifen, um Teilzeichenfolgen zu generieren.

• Schritt 3 – Die äußere Schleife beginnt bei i = 0 und subtrahiert die Stringlänge um 1.

• Schritt 4 – Innere Schleife beginnt bei j = 0 und subtrahiert die Stringlänge um 1.

• Schritt 5 – Konstruieren Sie eine Zählvariable mit dem Nullwert.

• Schritt 6– Erstellen Sie innerhalb der äußeren Schleife eine Variable „distinct_character“.

• Schritt 7 – Frequenzarray erstellen.

• Schritt 8– Alle Elemente auf Null setzen.

• Schritt 9 – Überprüfen Sie, ob die Häufigkeit von string[j] – „a“ Null ist.

• Schritt 10 − Wenn es Null ist, erhöhen Sie es um 1.

• Schritt 11 − Andernfalls teilen Sie es in eine innere Schleife auf.

• Schritt 12 – Wenn die Zählung größer als Null ist, geben Sie die Zählung zurück.

• Schritt 13 – Andernfalls geben Sie -1 zurück.

• Schritt 14 – Kündigung.

Syntax zum Erstellen aller verschiedenen Teilzeichenfolgen

string.substring(start, end)

In dieser Syntax können wir sehen, wie man minimale Änderungen an einer Zeichenfolge vornimmt, sodass alle Teilzeichenfolgen unterschiedlich sind.

• Parameter

• Start – Eine Startposition muss angegeben werden. Der Index des ersten Zeichens ist hier 0.

• End – Es handelt sich um einen optionalen Prozess am Ende (einschließlich, aber nicht beschränkt auf).

Methode

Methode 1 − Ermitteln Sie die Mindestanzahl an Änderungen, die alle Teilzeichenfolgen der Zeichenfolge unterschiedlich machen.

Finden Sie die Mindestanzahl an Änderungen, sodass alle Teilzeichenfolgen einer Zeichenfolge unterschiedlich werden

In dieser Methode lernen wir, wie man alle Teilzeichenfolgen unterschiedlich macht. Hier muss jeder Charakter anders sein. Wir müssen nur die Anzahl der Zeichen ermitteln. Wenn die Länge des Strings mehr als 26 beträgt, müssen wir ihn nur in einen String konvertieren. Hier werden wir dieselbe Logik an verschiedenen Orten schreiben.

Beispiel 1: Verwendung von 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;
}

Ausgabe

11

Beispiel 2: Durch die Verwendung von 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));
   }
}

Ausgabe

11

Beispiel 1: Verwendung von 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))
	

Ausgabe

11

Fazit

Heute haben wir in diesem Artikel gelernt, wie man mit minimalen Änderungen alle Teilzeichenfolgen unterschiedlich macht. Hier haben wir einige mögliche Codes erstellt, indem wir dem beschriebenen Algorithmus in C++, Java und Python gefolgt sind. Wir hoffen, dass Ihnen dies dabei hilft, ein umfassenderes Verständnis des Themas zu erlangen.

Das obige ist der detaillierte Inhalt vonÄndern Sie eine Zeichenfolge minimal, sodass alle Teilzeichenfolgen unterschiedlich sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!