Dada una string binaria S y una array A[] , ambas de tamaño N , la tarea es encontrar la puntuación máxima posible eliminando substrings de cualquier longitud, digamos K , que constan de los mismos caracteres y agregando A[K] a la puntaje.
Ejemplos:
Entrada: S = “abb”, A = [1, 3, 1]
Salida: 4
Explicación:
Inicialmente, puntuación = 0 y S=”abb”
Quite la substring {S[1], .. S[2]}, de longitud 2, y suma A[2] para puntuar. Por lo tanto, S se modifica a «a». Puntuación = 3.
Elimine la substring {S[0]}, de longitud 1, y agregue A[1] a la puntuación. Por lo tanto, S se modifica a «». Puntuación = 4.Entrada: S = “abb”, A = [2, 3, 1]
Salida: 6
Explicación:
Inicialmente, puntuación = 0 y S=”abb”.
Elimine la substring {S[2]}, de longitud 1, y agregue A[1] para puntuar. Por lo tanto, S se modifica a «ab». Puntuación = 1
Elimine la substring {S[1]}, de longitud 1, y agregue A[1] a la puntuación. Por lo tanto, S se modifica a «a». Puntuación = 4
Elimine la substring {S[0]}, de longitud 1, y agregue A[1] a la puntuación. Por lo tanto, S se modifica a «». Puntuación = 6
Enfoque ingenuo: la idea más simple para resolver este problema es usar Recursion . Iterar sobre los caracteres de la string . Si se encuentra una substring que consta solo de un carácter distinto, continúe con la búsqueda o elimine la substring y llame recursivamente a la función para la string restante.
A continuación se muestra la implementación del enfoque anterior:
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 not
bool 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 substrings
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.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 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))
C#
// C# program for the above approach
using 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 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>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Memoización para almacenar el resultado de las llamadas recursivas y usar la técnica de dos punteros para almacenar la substring que consta solo de 1 carácter distinto.
Siga los pasos a continuación para resolver el problema:
- Declare una función recursiva que tome la string como entrada para encontrar el resultado requerido.
- Inicialice una array, diga dp[] para memorizar los resultados.
- Si el valor ya está almacenado en la array dp[] , devuelva el resultado.
- De lo contrario, realice los siguientes pasos:
- Considerando el caso base si el tamaño de la string es 0, devuelve 0 . Si es igual a 1 , devuelve A[1] .
- Inicialice una variable, digamos res , para almacenar el resultado de la llamada de función actual.
- Inicialice dos punteros , digamos cabeza y cola , que denotan los índices inicial y final de la substring.
- Genere substrings que satisfagan la condición dada y, para cada substring, llame recursivamente a la función para la string restante. Guarda la puntuación máxima en res .
- Almacene el resultado en la array dp[] y devuélvalo.
- Imprime el valor devuelto por la función como resultado.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mukulbindal170299 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA