Dadas dos strings A y B de todas las letras mayúsculas, la tarea es encontrar si es posible hacer que la string A sea estrictamente lexicográficamente más pequeña que la string B intercambiando como máximo un par de caracteres en A.
Ejemplos:
Entrada: A = “OTRA VEZ”, B = “ACCIÓN”
Salida: Sí
Explicación:
Podemos hacer que la string A sea estrictamente lexicográficamente más pequeña que la string B intercambiando G y A (AAGIN)
AAGIN es lexicográficamente más pequeña que ACCIÓN
Entrada: A = “MANZANA” B = “AAAAPPPLLE”
Salida: No
Acercarse:
- Ordenar string A.
- Podemos encontrar la primera posición donde A y sorted(A) no coinciden.
- Luego encontramos la letra que debería estar en esa posición y la intercambiamos con la letra ordenada (A).
- Si hay varias opciones, es mejor tomar la última, ya que hace que la string resultante sea más pequeña.
- Ahora, compare la string A y la string B.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program check whether is
// it possible to make string A
// lexicographically smaller than string B
#include <bits/stdc++.h>
using namespace std;
// Swap function
void swap(char& x, char& y)
{
char temp = x;
x = y;
y = temp;
}
// Function that finds whether is
// it possible to make string A
// lexicographically smaller than string B
bool IsLexicographicallySmaller(
string A, string B)
{
// Condition if string A
// is already smaller than B
if (A < B) {
return true;
}
string temp = A;
// Sorting temp string
sort(temp.begin(), temp.end());
int index = -1;
for (int i = 0; i < A.length(); i++) {
// Condition for first changed
// character of string A and temp
if (A[i] != temp[i]) {
index = i;
break;
}
}
// Condition if string A
// is already sorted
if (index == -1) {
return false;
}
int j;
// Finding first changed character
// from last of string A
for (int i = 0; i < A.length(); i++) {
if (A[i] == temp[index])
j = i;
}
// Swap the two characters
swap(A[index], A[j]);
// Condition if string A
// is smaller than B
if (A < B) {
return true;
}
else {
return false;
}
}
// Driver Code
int main()
{
string A = "AGAIN";
string B = "ACTION";
if (IsLexicographicallySmaller(A, B)) {
cout << "Yes"
<< "\n";
}
else {
cout << "No"
<< "\n";
}
return 0;
}
Java
// Java program check whether is
// it possible to make String A
// lexicographically smaller than String B
import java.util.*;
class GFG{
// Swap function
static String swap(String str, int i, int j)
{
char[] tempArr = str.toCharArray();
char temp = tempArr[i];
tempArr[i] = tempArr[j];
tempArr[j] = temp;
return String.valueOf(tempArr);
}
// Function that finds whether is
// it possible to make String A
// lexicographically smaller than String B
static boolean IsLexicographicallySmaller(String A, String B)
{
// Condition if String A
// is already smaller than B
if (A.compareTo(B) < 0) {
return true;
}
String temp = A;
char p[] = temp.toCharArray();
// Sorting temp String
Arrays.sort(p);
temp=String.valueOf(p);
int index = -1;
for (int i = 0; i < A.length(); i++) {
// Condition for first changed
// character of String A and temp
if (A.charAt(i) != temp.charAt(i)) {
index = i;
break;
}
}
// Condition if String A
// is already sorted
if (index == -1) {
return false;
}
int j = 0;
// Finding first changed character
// from last of String A
for (int i = 0; i < A.length(); i++) {
if (A.charAt(i) == temp.charAt(index))
j = i;
}
// Swap the two characters
A = swap(A, index, j);
// Condition if String A
// is smaller than B
if (A.compareTo(B) < 0) {
return true;
}
else {
return false;
}
}
// Driver Code
public static void main(String args[])
{
String A = "AGAIN";
String B = "ACTION";
if (IsLexicographicallySmaller(A, B)) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
}
// This code is contributed by AbhiThakur
Python3
# Python3 program check
# it possible to make string
# A lexicographically smaller
# than string B
# Function that finds whether is
# it possible to make string A
# lexicographically smaller than
# string B
def IsLexicographicallySmaller(A, B):
# Condition if string A
# is already smaller
# than B
if(A < B):
return True
temp = A
# Sorting temp string
temp = ''.join(sorted(temp))
index =- 1
for i in range(len(A)):
# Condition for first
# changed character of
# string A and temp
if(A[i] != temp[i]):
index = i
break
# Condition if string A
# is already sorted
if(index == -1):
return False
j = 0
# Finding first changed
# character from last
# of string A
for i in range(len(A)):
if(A[i] == temp[index]):
j = i
A = list(A)
# Swap the two characters
A[index], A[j] = A[j], A[index]
A = ''.join(A)
# Condition if string A
# is smaller than B
if(A < B):
return True
else:
return False
# Driver Code
A = "AGAIN"
B = "ACTION"
if(IsLexicographicallySmaller(A, B)):
print("Yes")
else:
print("No")
# This code is contributed by avanitrachhadiya2155
C#
// C# program check whether is
// it possible to make String A
// lexicographically smaller
// than String B
using System;
class GFG{
// Swap function
static string swap(string str,
int i, int j)
{
char[] tempArr = str.ToCharArray();
char temp = tempArr[i];
tempArr[i] = tempArr[j];
tempArr[j] = temp;
return new string(tempArr);
}
// Function that finds whether is
// it possible to make String A
// lexicographically smaller than String B
static bool IsLexicographicallySmaller(string A,
string B)
{
// Condition if String A
// is already smaller than B
if (A.CompareTo(B) < 0)
{
return true;
}
string temp = A;
char []p = temp.ToCharArray();
// Sorting temp String
Array.Sort(p);
temp=new string(p);
int index = -1;
for (int i = 0; i < A.Length; i++)
{
// Condition for first changed
// character of String A and temp
if (A[i] != temp[i])
{
index = i;
break;
}
}
// Condition if String A
// is already sorted
if (index == -1)
{
return false;
}
int j = 0;
// Finding first changed character
// from last of String A
for (int i = 0; i < A.Length; i++)
{
if (A[i] == temp[index])
j = i;
}
// Swap the two characters
A = swap(A, index, j);
// Condition if String A
// is smaller than B
if (A.CompareTo(B) < 0)
{
return true;
}
else
{
return false;
}
}
// Driver Code
public static void Main(string []args)
{
string A = "AGAIN";
string B = "ACTION";
if (IsLexicographicallySmaller(A, B))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by Rutvik_56
Javascript
<script>
// Javascript program check whether is
// it possible to make String A
// lexicographically smaller than String B
// Swap function
function swap(str,i,j)
{
let tempArr = str.split("");
let temp = tempArr[i];
tempArr[i] = tempArr[j];
tempArr[j] = temp;
return (tempArr).join("");
}
// Function that finds whether is
// it possible to make String A
// lexicographically smaller than String B
function IsLexicographicallySmaller(A, B)
{
// Condition if String A
// is already smaller than B
if (A < (B) ) {
return true;
}
let temp = A;
let p = temp.split("");
// Sorting temp String
p.sort();
temp=(p).join("");
let index = -1;
for (let i = 0; i < A.length; i++) {
// Condition for first changed
// character of String A and temp
if (A[i] != temp[i]) {
index = i;
break;
}
}
// Condition if String A
// is already sorted
if (index == -1) {
return false;
}
let j = 0;
// Finding first changed character
// from last of String A
for (let i = 0; i < A.length; i++) {
if (A[i] == temp[index])
j = i;
}
// Swap the two characters
A = swap(A, index, j);
// Condition if String A
// is smaller than B
if (A < (B) ) {
return true;
}
else {
return false;
}
}
// Driver Code
let A = "AGAIN";
let B = "ACTION";
if (IsLexicographicallySmaller(A, B)) {
document.write("Yes");
}
else {
document.write("No");
}
// This code is contributed by ab2127
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA