Höchstmögliche Punktzahl durch Entfernen von Teilzeichenfolgen, die aus einzelnen unterschiedlichen Zeichen bestehen
Bei einer binären Zeichenfolge S und einem Array A[] , beide der Größe N , besteht die Aufgabe darin, die maximal mögliche Punktzahl zu finden, indem Teilzeichenfolgen beliebiger Länge entfernt werden, sagen wir K , die aus denselben Zeichen bestehen, und A[K] zu hinzugefügt werden Ergebnis.
Beispiele:
Input: S = „abb“, A = [1, 3, 1]
Output: 4
Erklärung:
Initial, score = 0 und S=“abb“
Entferne den Teilstring {S[1], .. S[2]}, der Länge 2, und fügen Sie A[2] hinzu, um zu punkten. Daher ändert sich S zu „a“. Ergebnis = 3.
Entfernen Sie die Teilzeichenfolge {S[0]} der Länge 1 und fügen Sie A[1] hinzu, um zu bewerten. Daher ändert sich S in „“. Punktzahl = 4.Eingabe: S = „abb“, A = [2, 3, 1]
Ausgabe: 6
Erklärung:
Anfänglich Punktzahl = 0 und S = „abb“.
Entfernen Sie die Teilzeichenfolge {S[2]} der Länge 1 und fügen Sie A[1] hinzu, um zu punkten. Daher ändert sich S zu „ab“. Punktzahl = 1
Entfernen Sie den Teilstring {S[1]} der Länge 1 und fügen Sie A[1] hinzu, um die Punktzahl zu erhalten. Daher ändert sich S zu „a“. Ergebnis = 4
Entfernen Sie die Teilzeichenfolge {S[0]} der Länge 1 und fügen Sie A[1] hinzu, um zu bewerten. Daher ändert sich S in „“. Punktzahl = 6
Naiver Ansatz: Die einfachste Idee zur Lösung dieses Problems ist die Verwendung von Recursion . Iterieren Sie über die Zeichen der Zeichenfolge . Wenn eine Teilzeichenfolge gefunden wird, die nur aus einem eindeutigen Zeichen besteht, fahren Sie entweder mit fort, um die Suche fortzusetzen, oder entfernen Sie die Teilzeichenfolge und rufen Sie rekursiv die Funktion für die verbleibende Zeichenfolge auf.
Unten ist die Implementierung des obigen Ansatzes:
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if the string s consists // of a single distinct character or not static boolean isUnique(String s) { HashSet<Character> set = new HashSet<>(); for (char c : s.toCharArray()) set.add(c); return set.size() == 1; } // Function to calculate the maximum // score possible by removing substrings static int maxScore(String s, int[] a) { int n = s.length(); // If string is empty if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Store the maximum result int mx = -1; // Try to remove all substrings that // satisfy the condition and check // for resultant string after removal for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Store the substring {s[i], .., s[j]} String sub = s.substring(i, j + 1); // Check if the substring contains // only a single distinct character if (isUnique(sub)) mx = Math.max( mx, a[sub.length() - 1] + maxScore( s.substring(0, i) + s.substring(j + 1), a)); } } // Return the maximum score return mx; } // Driver Code public static void main(String args[]) { String s = "011"; int a[] = { 1, 3, 1 }; System.out.print(maxScore(s, a)); } } // This code is contributed by hemanth gadarla.
Python3
# Python program for the above approach # Function to check if the string s consists # of a single distinct character or not def isUnique(s): return True if len(set(s)) == 1 else False # Function to calculate the maximum # score possible by removing substrings def maxScore(s, a): n = len(s) # If string is empty if n == 0: return 0 # If length of string is 1 if n == 1: return a[0] # Store the maximum result mx = -1 # Try to remove all substrings that # satisfy the condition and check # for resultant string after removal for i in range(n): for j in range(i, n): # Store the substring {s[i], .., s[j]} sub = s[i:j + 1] # Check if the substring contains # only a single distinct character if isUnique(sub): mx = max(mx, a[len(sub)-1] + maxScore(s[:i]+s[j + 1:], a)) # Return the maximum score return mx # Driver Code if __name__ == "__main__": s = "011" a = [1, 3, 1] print(maxScore(s, a))
Javascript
<script> // JavaScript program for the above approach // Function to check if the string s consists // of a single distinct character or not function isUnique( s) { var set = new Set(); for(let i = 0 ; i< s.length ; i++) { set.add(s[i]); } return set.size == 1; } // Function to calculate the maximum // score possible by removing substrings function maxScore( s, a) { let n = s.length; // If string is empty if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Store the maximum result let mx = -1; // Try to remove all substrings that // satisfy the condition and check // for resultant string after removal for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { // Store the substring {s[i], .., s[j]} let sub = s.substring(i, j + 1); // Check if the substring contains // only a single distinct character if (isUnique(sub)) mx = Math.max( mx, a[sub.length - 1] + maxScore( s.substring(0, i) + s.substring(j + 1), a)); } } // Return the maximum score return mx; } // Driver Code let s = "011"; let a = [ 1, 3, 1 ]; document.write(maxScore(s, a)); </script>
4
Zeitkomplexität: O(N 2 )
Hilfsraum: O(1)
Effizienter Ansatz: Um den obigen Ansatz zu optimieren, besteht die Idee darin, Memoization zu verwenden, um das Ergebnis der rekursiven Aufrufe zu speichern, und die Zwei-Zeiger-Technik zu verwenden, um die Teilzeichenfolge zu speichern, die nur aus einem eindeutigen Zeichen besteht.
Führen Sie die folgenden Schritte aus, um das Problem zu lösen:
- Deklarieren Sie eine rekursive Funktion , die die Zeichenfolge als Eingabe verwendet, um das erforderliche Ergebnis zu finden.
- Initialisieren Sie ein Array, sagen Sie dp[] , um die Ergebnisse zu speichern.
- Wenn der Wert bereits im Array dp[] gespeichert ist , geben Sie das Ergebnis zurück.
- Führen Sie andernfalls die folgenden Schritte aus:
- Unter Berücksichtigung des Basisfalls, wenn die Größe der Zeichenfolge 0 ist , geben Sie 0 zurück . Wenn es gleich 1 ist, gib A[1] zurück .
- Initialisieren Sie eine Variable, sagen wir res , um das Ergebnis des aktuellen Funktionsaufrufs zu speichern.
- Initialisieren Sie zwei Zeiger , z. B. head und tail , die den Start- und Endindex der Teilzeichenfolge bezeichnen.
- Generieren Sie Teilstrings , die die gegebene Bedingung erfüllen, und rufen Sie für jeden Teilstring rekursiv die Funktion für den verbleibenden String auf. Speichern Sie die maximale Punktzahl in res .
- Speichern Sie das Ergebnis im Array dp[] und geben Sie es zurück.
- Geben Sie den von der Funktion zurückgegebenen Wert als Ergebnis aus.
Unten ist die Implementierung des obigen Ansatzes:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Initialize a dictionary to // store the precomputed results map<string,int> dp; // Function to calculate the maximum // score possible by removing substrings int maxScore(string s, vector<int> a) { // If s is present in dp[] array if (dp.find(s) != dp.end()) return dp[s]; // Base Cases: int n = s.size(); // If length of string is 0 if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Put head pointer at start int head = 0; // Initialize the max variable int mx = -1; // Generate the substrings // using two pointers while (head < n) { int tail = head; while (tail < n) { // If s[head] and s[tail] // are different if (s[tail] != s[head]) { // Move head to // tail and break head = tail; break; } // Store the substring string sub = s.substr(head, tail + 1); // Update the maximum mx = max(mx, a[sub.size() - 1] + maxScore(s.substr(0, head) + s.substr(tail + 1,s.size()), a)); // Move the tail tail += 1; } if (tail == n) break; } // Store the score dp[s] = mx; return mx; } // Driver Code int main() { string s = "abb"; vector<int> a = {1, 3, 1}; cout<<(maxScore(s, a)-1); } // This code is contributed by mohit kumar 29.
Java
// Java program for the above approach import java.util.*; class GFG{ // Initialize a dictionary to // store the precomputed results static Map<String, Integer> dp = new HashMap<>(); // Function to calculate the maximum // score possible by removing substrings static int maxScore(String s, int[] a) { // If s is present in dp[] array if (dp.containsKey(s)) return dp.get(s); // Base Cases: int n = s.length(); // If length of string is 0 if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Put head pointer at start int head = 0; // Initialize the max variable int mx = -1; // Generate the substrings // using two pointers while (head < n) { int tail = head; while (tail < n) { // If s[head] and s[tail] // are different if (s.charAt(tail) != s.charAt(head)) { // Move head to // tail and break head = tail; break; } // Store the substring String sub = s.substring(head, tail + 1); // Update the maximum mx = Math.max( mx, a[sub.length() - 1] + maxScore(s.substring(0, head) + s.substring(tail + 1, s.length()), a)); // Move the tail tail += 1; } if (tail == n) break; } // Store the score dp.put(s, mx); return mx; } // Driver code public static void main(String[] args) { String s = "abb"; int[] a = { 1, 3, 1 }; System.out.println((maxScore(s, a))); } } // This code is contributed by offbeat
Python3
# Python program for the above approach # Initialize a dictionary to # store the precomputed results dp = dict() # Function to calculate the maximum # score possible by removing substrings def maxScore(s, a): # If s is present in dp[] array if s in dp: return dp[s] # Base Cases: n = len(s) # If length of string is 0 if n == 0: return 0 # If length of string is 1 if n == 1: return a[0] # Put head pointer at start head = 0 # Initialize the max variable mx = -1 # Generate the substrings # using two pointers while head < n: tail = head while tail < n: # If s[head] and s[tail] # are different if s[tail] != s[head]: # Move head to # tail and break head = tail break # Store the substring sub = s[head:tail + 1] # Update the maximum mx = max(mx, a[len(sub)-1] + maxScore(s[:head] + s[tail + 1:], a)) # Move the tail tail += 1 if tail == n: break # Store the score dp[s] = mx return mx # Driver Code if __name__ == "__main__": s = "abb" a = [1, 3, 1] print(maxScore(s, a))
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Initialize a dictionary to // store the precomputed results static Dictionary<string, int> dp = new Dictionary<string, int>(); // Function to calculate the maximum // score possible by removing substrings static int maxScore(string s, int[] a) { // If s is present in dp[] array if (dp.ContainsKey(s)) return dp[s]; // Base Cases: int n = s.Length; // If length of string is 0 if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Put head pointer at start int head = 0; // Initialize the max variable int mx = -1; // Generate the substrings // using two pointers while (head < n) { int tail = head; while (tail < n) { // If s[head] and s[tail] // are different if (s[tail] != s[head]) { // Move head to // tail and break head = tail; break; } // Store the substring string sub = s.Substring(head, tail + 1-head); // Update the maximum mx = Math.Max( mx, a[sub.Length - 1] + maxScore(s.Substring(0, head) + s.Substring(tail + 1, s.Length-tail - 1), a)); // Move the tail tail += 1; } if (tail == n) break; } // Store the score dp.Add(s, mx); return mx; } // Driver code static public void Main() { string s = "abb"; int[] a = { 1, 3, 1 }; Console.WriteLine((maxScore(s, a))); } } // This code is contributed by patel2127
Javascript
<script> // JavaScript program for the above approach // Initialize a dictionary to // store the precomputed results let dp = new Map(); // Function to calculate the maximum // score possible by removing substrings function maxScore(s, a) { // If s is present in dp[] array if (dp.has(s)) return dp.get(s); // Base Cases: let n = s.length; // If length of string is 0 if (n == 0) return 0; // If length of string is 1 if (n == 1) return a[0]; // Put head pointer at start let head = 0; // Initialize the max variable let mx = -1; // Generate the substrings // using two pointers while (head < n) { let tail = head; while (tail < n) { // If s[head] and s[tail] // are different if (s[tail] != s[head]) { // Move head to // tail and break head = tail; break; } // Store the substring let sub = s.substring(head, head + tail + 1); // Update the maximum mx = Math.max( mx, a[sub.length - 1] + maxScore(s.substring(0, head) + s.substring(tail + 1, tail + 1 + s.length), a)); // Move the tail tail += 1; } if (tail == n) break; } // Store the score dp.set(s, mx); return mx; } let s = "abb"; let a = [ 1, 3, 1 ]; document.write((maxScore(s, a))-1); </script>
4
Zeitkomplexität: O(N)
Hilfsraum: O(N)
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .