Dados muchos N dígitos. También nos dan 10 números que representan el número alternativo para todos los números de un dígito del 0 al 9 . Podemos reemplazar cualquier dígito en N con el dígito alternativo dado, pero solo se nos permite reemplazar cualquier segmento consecutivo de números por una sola vez, la tarea es reemplazar cualquier segmento consecutivo de números tal que el número obtenido sea el mayor de todos los reemplazos posibles.
Ejemplos:
Entrada: n = 1337, a[] = {0, 1, 2, 5, 4, 6, 6, 3, 1, 9}
Salida: 1557
1 se puede reemplazar con 1 como a[1] = 1 (Sin efecto )
3 se puede reemplazar con 5
7 se puede reemplazar con 3 (no es obligatorio si el número debe maximizarse)
Entrada: número = 11111, a[] = {0, 5, 2, 5, 4, 6, 6 , 3, 1, 9}
Salida: 55555
Enfoque: dado que necesitamos obtener el número más grande posible, iterar desde la izquierda y encontrar el número cuyo número alternativo sea mayor que el actual, y seguir reemplazando los números siguientes hasta que el número alternativo no sea más pequeño.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximized number
string get_maximum(string s, int a[])
{
int n = s.size();
// Iterate till the end of the string
for (int i = 0; i < n; i++) {
// Check if it is greater or not
if (s[i] - '0' < a[s[i] - '0']) {
int j = i;
// Replace with the alternate till smaller
while (j < n && (s[j] - '0' <= a[s[j] - '0'])) {
s[j] = '0' + a[s[j] - '0'];
j++;
}
return s;
}
}
// Return original s in case
// no change took place
return s;
}
// Driver Code
int main()
{
string s = "1337";
int a[] = { 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 };
cout << get_maximum(s, a);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the maximized number
static String get_maximum(char[] s, int a[])
{
int n = s.length;
// Iterate till the end of the string
for (int i = 0; i < n; i++)
{
// Check if it is greater or not
if (s[i] - '0' < a[s[i] - '0'])
{
int j = i;
// Replace with the alternate till smaller
while (j < n && (s[j] - '0' <= a[s[j] - '0']))
{
s[j] = (char) ('0' + a[s[j] - '0']);
j++;
}
return String.valueOf(s);
}
}
// Return original s in case
// no change took place
return String.valueOf(s);
}
// Driver Code
public static void main(String[] args)
{
String s = "1337";
int a[] = { 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 };
System.out.println(get_maximum(s.toCharArray(), a));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
# Function to return the maximized number
def get_maximum(s, a) :
s = list(s)
n = len(s)
# Iterate till the end of the string
for i in range(n) :
# Check if it is greater or not
if (ord(s[i]) - ord('0') < a[ord(s[i]) - ord('0')]) :
j = i
# Replace with the alternate till smaller
while (j < n and (ord(s[j]) - ord('0') <=
a[ord(s[j]) - ord('0')])) :
s[j] = chr(ord('0') + a[ord(s[j]) - ord('0')])
j += 1
return "".join(s);
# Return original s in case
# no change took place
return s
# Driver Code
if __name__ == "__main__" :
s = "1337"
a = [ 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 ]
print(get_maximum(s, a))
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximized number
static String get_maximum(char[] s, int[] a)
{
int n = s.Length;
// Iterate till the end of the string
for (int i = 0; i < n; i++)
{
// Check if it is greater or not
if (s[i] - '0' < a[s[i] - '0'])
{
int j = i;
// Replace with the alternate till smaller
while (j < n && (s[j] - '0' <= a[s[j] - '0']))
{
s[j] = (char) ('0' + a[s[j] - '0']);
j++;
}
return String.Join("",s);
}
}
// Return original s in case
// no change took place
return String.Join("",s);
}
// Driver Code
public static void Main(String[] args)
{
String s = "1337";
int[] a = { 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 };
Console.WriteLine(get_maximum(s.ToCharArray(), a));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to return the maximized number
function get_maximum($s, $a)
{
$n = strlen($s);
// Iterate till the end of the string
for ($i = 0; $i < $n; $i++)
{
// Check if it is greater or not
if ($s[$i] - '0' < $a[$s[$i] - '0'])
{
$j = $i;
// Replace with the alternate till smaller
while ($j < $n && ($s[$j] - '0' <= $a[$s[$j] - '0']))
{
$s[$j] = '0' + $a[$s[$j] - '0'];
$j++;
}
return $s;
}
}
// Return original s in case
// no change took place
return $s;
}
// Driver Code
$s = "1337";
$a = array( 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 );
echo get_maximum($s, $a);
// This Code is contributed is Tushill.
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximized number
function get_maximum(s, a)
{
let n = s.length;
// Iterate till the end of the string
for (let i = 0; i < n; i++)
{
// Check if it is greater or not
if (s[i].charCodeAt() - '0'.charCodeAt()
< a[s[i].charCodeAt() - '0'.charCodeAt()])
{
let j = i;
// Replace with the alternate till smaller
while (j < n && (s[j].charCodeAt() - '0'.charCodeAt()
<= a[s[j].charCodeAt() - '0'.charCodeAt()]))
{
s[j] = String.fromCharCode('0'.charCodeAt()
+ a[s[j].charCodeAt() - '0'.charCodeAt()]);
j++;
}
return s.join("");
}
}
// Return original s in case
// no change took place
return s.join("");
}
let s = "1337";
let a = [ 0, 1, 2, 5, 4, 6, 6, 3, 1, 9 ];
document.write(get_maximum(s.split(''), a));
</script>
1557
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)