Given a binary string S and an array A[], both of size N, the task is to find the maximum score possible by removing substrings of any length, say K, consisting of the same characters, and adding A[K] to the score.
Examples:
Input: S = “abb”, A = [1, 3, 1]
Output: 4
Explanation:
Initially, score = 0 and S=”abb”
Remove the substring {S[1], .. S[2]}, of length 2, and add A[2] to score. Therefore, S modifies to “a”. Score = 3.
Remove the substring {S[0]}, of length 1, and add A[1] to score. Therefore, S modifies to “”. Score = 4.Input: S = “abb”, A = [2, 3, 1]
Output: 6
Explanation:
Initially, score = 0 and S=”abb”.
Remove the substring {S[2]}, of length 1, and add A[1] to score. Therefore, S modifies to “ab”. Score = 1
Remove the substring {S[1]}, of length 1, and add A[1] to score. Therefore, S modifies to “a”. Score = 4
Remove the substring {S[0]}, of length 1, and add A[1] to score. Therefore, S modifies to “”. Score = 6
Naive Approach: The simplest idea is to solve this problem is to use Recursion. Iterate over the characters of the string. If a substring consisting only of one distinct character is encountered, then proceed with either to continue the search or to remove the substring and recursively call the function for the remaining string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the string s consists// of a single distinct character or notbool isUnique(string s){ set<char> Set; for(char c : s) { Set.insert(c); } return Set.size() == 1;}// Function to calculate the maximum// score possible by removing substringsint 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.substr(i, j + 1); // Check if the substring contains // only a single distinct character if (isUnique(sub)) mx = max(mx, a[sub.length() - 1] + maxScore(s.substr(0, i) + s.substr(j + 1), a)); } } // Return the maximum score return mx;} int main(){ string s = "011"; int a[] = { 1, 3, 1 }; cout << maxScore(s, a)-1; return 0;}// This code is contributed by mukesh07. |
Java
// Java program for the above approachimport 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 notdef isUnique(s): return True if len(set(s)) == 1 else False# Function to calculate the maximum# score possible by removing substringsdef 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 Codeif __name__ == "__main__": s = "011" a = [1, 3, 1] print(maxScore(s, a)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if the string s consists // of a single distinct character or not static bool isUnique(string s) { HashSet<char> set = new HashSet<char>(); foreach(char c in s) set.Add(c); return set.Count == 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 - i); // 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 static void Main() { string s = "011"; int[] a = { 1, 3, 1 }; Console.Write(maxScore(s, a)); }}// This code is contributed by suresh07. |
Javascript
<script>// JavaScript program for the above approach // Function to check if the string s consists// of a single distinct character or notfunction 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 substringsfunction 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 Codelet s = "011";let a = [ 1, 3, 1 ];document.write(maxScore(s, a)); </script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Memoization to store the result of the recursive calls and use Two pointer technique to store the substring consisting only of 1 distinct character.
Follow the steps below to solve the problem:
- Declare a recursive function that takes the string as the input to find the required result.
- Initialize an array, say dp[] to memorize the results.
- If the value is already stored in the array dp[], return the result.
- Otherwise, perform the following steps:
- Considering the base case if the size of the string is 0, return 0. If it is equal to 1, return A[1].
- Initialize a variable, say res, to store the result of the current function call.
- Initialize two pointers, say head and tail, denoting the starting and ending indices of the substring.
- Generate substrings satisfying the given condition, and for each substring, recursively call the function for the remaining string. Store the maximum score in res.
- Store the result in the dp[] array and return it.
- Print the value returned by the function as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Initialize a dictionary to// store the precomputed resultsmap<string,int> dp;// Function to calculate the maximum// score possible by removing substringsint 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 Codeint 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 approachimport java.util.*;class GFG{ // Initialize a dictionary to// store the precomputed resultsstatic Map<String, Integer> dp = new HashMap<>();// Function to calculate the maximum// score possible by removing substringsstatic 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 resultsdp = dict()# Function to calculate the maximum# score possible by removing substringsdef 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 Codeif __name__ == "__main__": s = "abb" a = [1, 3, 1] print(maxScore(s, a)) |
C#
// C# program for the above approachusing 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 substringsstatic 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 codestatic 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> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
