Dadas dos strings str1 y str2 , la tarea es contar los caracteres en str1 de manera que después de eliminar cualquiera de ellos, str1 se vuelve idéntico a str2 . Además, imprima las posiciones de estos caracteres. Si no es posible, imprima -1 .
Ejemplos:
Entrada: str1 = “abdrakadabra”, str2 = “abrakadabra”
Salida: 1
El único carácter válido está en el índice 2, es decir, str1[2]
Entrada: str1 = “aa”, str2 = “a”
Salida: 2
Entrada: str1 = “ geeksforgeeks”, str2 = “competiciones”
Salida: 0
Enfoque: encuentre la longitud del prefijo común más largo, sea l, y la longitud del sufijo común más largo, sea r de dos strings. La solución claramente no es posible si
- len(string) != len(string2) + 1
- len(str1) + 1 < norte – r
De lo contrario, los índices válidos son de max(len(str1) – r, 1) a min(l + 1, len(str1))
A continuación se muestra la implementación del enfoque anterior:
C++
// Below is C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of required indices
int Find_Index(string str1, string str2)
{
int n = str1.size();
int m = str2.size();
int l = 0;
int r = 0;
// Solution doesn't exist
if (n != m + 1) {
return -1;
}
// Find the length of the longest
// common prefix of strings
for (int i = 0; i < m; i++) {
if (str1[i] == str2[i]) {
l += 1;
}
else {
break;
}
}
// Find the length of the longest
// common suffix of strings
int i = n - 1;
int j = m - 1;
while (i >= 0 && j >= 0 && str1[i] == str2[j]) {
r += 1;
i -= 1;
j -= 1;
}
// If solution does not exist
if (l + r < m) {
return -1;
}
// Return the count of indices
else {
i = max(n - r, 1);
j = min(l + 1, n);
return (j - i + 1);
}
}
// Driver code
int main()
{
string str1 = "aaa", str2 = "aa";
cout << Find_Index(str1, str2);
return 0;
}
// This code is contributed by PrinciRaj1992
Java
// Java implementation of the approach
class GFG {
// Function to return the count
// of required indices
static int Find_Index(String str1, String str2)
{
int n = str1.length();
int m = str2.length();
int l = 0;
int r = 0;
// Solution doesn't exist
if (n != m + 1) {
return -1;
}
// Find the length of the longest
// common prefix of strings
for (int i = 0; i < m; i++) {
if (str1.charAt(i) == str2.charAt(i)) {
l += 1;
}
else {
break;
}
}
// Find the length of the longest
// common suffix of strings
int i = n - 1;
int j = m - 1;
while (i >= 0 && j >= 0
&& str1.charAt(i) == str2.charAt(j)) {
r += 1;
i -= 1;
j -= 1;
}
// If solution does not exist
if (l + r < m) {
return -1;
}
// Return the count of indices
else {
i = Math.max(n - r, 1);
j = Math.min(l + 1, n);
return (j - i + 1);
}
}
// Driver code
public static void main(String[] args)
{
String str1 = "aaa", str2 = "aa";
System.out.println(Find_Index(str1, str2));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function to return the count of required indices def Find_Index(str1, str2): n = len(str1) m = len(str2) l = 0 r = 0 # Solution doesn't exist if(n != m + 1): return -1 # Find the length of the longest # common prefix of strings for i in range(m): if str1[i] == str2[i]: l += 1 else: break # Find the length of the longest # common suffix of strings i = n-1 j = m-1 while i >= 0 and j >= 0 and str1[i] == str2[j]: r += 1 i -= 1 j -= 1 # If solution does not exist if l + r < m: return -1 # Return the count of indices else: i = max(n-r, 1) j = min(l + 1, n) return (j-i + 1) # Driver code if __name__ == "__main__": str1 = "aaa" str2 = "aa" print(Find_Index(str1, str2))
C#
// Program to print the given pattern
using System;
class GFG {
// Function to return the count
// of required indices
static int Find_Index(String str1, String str2)
{
int n = str1.Length;
int m = str2.Length;
int l = 0;
int r = 0;
int i, j;
// Solution doesn't exist
if (n != m + 1) {
return -1;
}
// Find the length of the longest
// common prefix of strings
for (i = 0; i < m; i++) {
if (str1[i] == str2[i]) {
l += 1;
}
else {
break;
}
}
// Find the length of the longest
// common suffix of strings
i = n - 1;
j = m - 1;
while (i >= 0 && j >= 0 && str1[i] == str2[j]) {
r += 1;
i -= 1;
j -= 1;
}
// If solution does not exist
if (l + r < m) {
return -1;
}
// Return the count of indices
else {
i = Math.Max(n - r, 1);
j = Math.Min(l + 1, n);
return (j - i + 1);
}
}
// Driver code
public static void Main(String[] args)
{
String str1 = "aaa", str2 = "aa";
Console.WriteLine(Find_Index(str1, str2));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to return the count
// of required indices
function Find_index(str1,str2)
{
var n = str1.length;
var m = str2.length;
var l = 0;
var r = 0;
// Solution doesn't exist
if (n != m + 1)
{
return -1;
}
// Find the length of the longest
// common prefix of strings
for (var i = 0; i < m; i++)
{
if (str1[i] == str2[i])
{
l += 1;
}
else
{
break;
}
}
// Find the length of the longest
// common suffix of strings
var i = n - 1;
var j = m - 1;
while (i >= 0 && j >= 0 &&
str1[i] == str2[j])
{
r += 1;
i -= 1;
j -= 1;
}
// If solution does not exist
if (l + r < m)
{
return -1;
}
// Return the count of indices
else
{
i = Math.max(n - r, 1);
j = Math.min(l + 1, n);
return (j - i + 1);
}
}
// Driver code
// Given Strings
var str1 = "aaa";
var str2 = "aa";
// Function call
var result = Find_index(str1,str2);
// Print the answer
document.write(result);
// This code is contributed by rj13to
</script>
Producción:
3
Complejidad de tiempo: O(n+m) // donde n es la longitud de la primera string y m es la longitud de la segunda string
Complejidad espacial: O(1) //no se usa espacio extra
Publicación traducida automáticamente
Artículo escrito por saurabh sisodia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA