Dadas dos strings s1 y s2 , la tarea es encontrar la longitud de la subsecuencia común más larga sin carácter repetido .
Ejemplos:
Entrada: s1= “aabbcc”, s2= “aabc”
Salida: 3
Explicación: “aabc” es la subsecuencia común más larga pero tiene dos caracteres repetidos ‘a’.
Entonces, la subsecuencia común más larga requerida sin carácter repetido es «abc».Entrada: s1= “aabcad”, s2= “adbcwcad”
Salida: 4
Explicación: Las subsecuencias son “abcd” o “bcad”.
Enfoque: el enfoque para resolver el problema es similar al de la subsecuencia común más larga usando la recursividad , pero también debe realizar un seguimiento de que no se repiten dos caracteres en una subsecuencia. Siga los pasos que se mencionan a continuación:
- Para cada carácter en la i-ésima posición, ese carácter puede ser parte de una secuencia o no.
- Genere cada secuencia de esta manera y busque la secuencia común más larga.
- Para realizar un seguimiento de los caracteres que se incluyen en la subsecuencia, use bits de la variable «almacenar» .
- Cada bit de la variable «almacenar» indica si ese alfabeto ya está presente o no en una subsecuencia.
- el bit en la posición 0 corresponde al carácter ‘a’, en la posición 1 corresponde a ‘b’, de manera similar 2 a ‘c’ y así sucesivamente.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find lcs
// with no repeating character
int find(string s1, string s2, int N,
int M, long long store)
{
if (N == 0 || M == 0)
return 0;
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1[N - 1] - 'a'))
& 1)
== 0) {
store = (store | (1 << (s1[N - 1]
- 'a')));
return 1 + find(s1, s2, N - 1,
M - 1, store);
}
else
return max(find(s1, s2, N - 1, M,
store),
find(s1, s2, N, M - 1,
store));
}
// Driver code
int main()
{
string s1, s2;
s1 = "aabbcc";
s2 = "aabc";
long long store = 0;
cout << find(s1, s2, s1.length(),
s2.length(), store);
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to find lcs
// with no repeating character
static int find(String s1, String s2, int N,
int M, int store) {
if (N == 0 || M == 0)
return 0;
if (s1.charAt(N - 1) == s2.charAt(M - 1)
&& ((store >> (s1.charAt(N - 1) - 'a'))
& 1) == 0) {
store = (store | (1 << (s1.charAt(N - 1) - 'a')));
return 1 + find(s1, s2, N - 1, M - 1, store);
}
else
return Math.max(find(s1, s2, N - 1, M, store),
find(s1, s2, N, M - 1, store));
}
// Driver Code
public static void main(String args[]) {
String s1, s2;
s1 = "aabbcc";
s2 = "aabc";
int store = 0;
System.out.println(find(s1, s2, s1.length(), s2.length(), store));
}
}
// This code is contributed by gfgking
Python3
# python3 program to implement the approach
# Function to find lcs
# with no repeating character
def find(s1, s2, N, M, store):
if (N == 0 or M == 0):
return 0
if (s1[N - 1] == s2[M - 1]
and ((store >> (ord(s1[N - 1]) - ord('a')))
& 1)
== 0):
store = (store | (1 << (ord(s1[N - 1]) - ord('a'))))
return 1 + find(s1, s2, N - 1,
M - 1, store)
else:
return max(find(s1, s2, N - 1, M,
store),
find(s1, s2, N, M - 1,
store))
# Driver code
if __name__ == "__main__":
s1 = "aabbcc"
s2 = "aabc"
store = 0
print(find(s1, s2, len(s1), len(s2), store))
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find lcs
// with no repeating character
static int find(string s1, string s2, int N,
int M, int store)
{
if (N == 0 || M == 0)
return 0;
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1[N - 1] - 'a'))
& 1)
== 0) {
store = (store | (1 << (s1[N - 1]
- 'a')));
return 1 + find(s1, s2, N - 1,
M - 1, store);
}
else
return Math.Max(find(s1, s2, N - 1, M,
store),
find(s1, s2, N, M - 1,
store));
}
// Driver Code
public static void Main(String[] args)
{
string s1, s2;
s1 = "aabbcc";
s2 = "aabc";
int store = 0;
Console.Write(find(s1, s2, s1.Length,
s2.Length, store));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript code for the above approach
// Function to find lcs
// with no repeating character
function find(s1, s2, N,
M, store) {
if (N == 0 || M == 0)
return 0;
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1[N - 1].charCodeAt(0) - 'a'.charCodeAt(0)))
& 1) == 0) {
store = (store | (1 << (s1[N - 1].charCodeAt(0) - 'a'.charCodeAt(0)
)));
return 1 + find(s1, s2, N - 1,
M - 1, store);
}
else
return Math.max(find(s1, s2, N - 1, M,
store),
find(s1, s2, N, M - 1,
store));
}
// Driver code
let s1, s2;
s1 = "aabbcc";
s2 = "aabc";
let store = 0;
document.write(find(s1, s2, s1.length,
s2.length, store));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad de tiempo: O (N * 2 N ) donde N es max (tamaño de s1, tamaño de s2).
Espacio Auxiliar: O(1)
Enfoque eficiente: un enfoque eficiente es utilizar la memorización para reducir la complejidad del tiempo. Cree una array 2D dp[][] donde dp[i][j] almacene la longitud de la subsecuencia común más larga sin carácter repetido hasta que se considere el i-ésimo índice de s1 y el j-ésimo índice de s2 . Si los caracteres en s1[i] y s2[j] son iguales entonces dp[i][j] = dp[i-1][j-1] + 1 , de lo contrario dp[i][j] = max(dp[ i-1][j], dp[i][j-1]) . Simplemente haga un seguimiento de los caracteres repetidos como se menciona en el enfoque anterior junto con esto.
Nota: En la implementación, la array dp se implementa utilizando map donde la clave es la string concatenada de i y j .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Map for memoization
map<string, int> mp;
// Function to find lcs
// with no repeating character
int find(string s1, string s2, int N, int M,
long long store)
{
if (N == 0 || M == 0)
return 0;
string temp = to_string(N) + '#'
+ to_string(M) + '#'
+ to_string(store);
if (mp.find(temp) != mp.end())
return mp[temp];
// If the characters are same
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1[N - 1] - 'a'))
& 1)
== 0) {
store = (store | (1 << (s1[N - 1]
- 'a')));
return mp[temp]
= 1 + find(s1, s2, N - 1,
M - 1, store);
}
// if the characters are different
else
return mp[temp]
= max(find(s1, s2, N - 1,
M, store),
find(s1, s2, N, M - 1,
store));
}
// Driver code
int main()
{
string s1, s2;
s1 = "aabbcc";
s2 = "aabc";
long long store = 0;
cout << find(s1, s2, s1.length(),
s2.length(), store);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Map for memoization
private static HashMap<String, Integer> mp = new HashMap<>();
// Function to find lcs
// with no repeating character
static int find(String s1, String s2, int N, int M,int store)
{
if (N == 0 || M == 0)
return 0;
String temp = String.valueOf(N) + '#'
+ String.valueOf(M) + '#'
+ String.valueOf(store);
if (mp.containsKey(temp))
return mp.get(temp);
// If the characters are same
if (s1.charAt(N - 1) == s2.charAt(M - 1)
&& ((store >> (s1.charAt(N - 1) - 'a'))
& 1)
== 0) {
store = (store | (1 << (s1.charAt(N - 1)- 'a')));
mp.put(temp,1 + find(s1, s2, N - 1,M - 1, store));
return mp.get(temp);
}
// if the characters are different
else
{ mp.put(temp,Math.max(find(s1, s2, N - 1,
M, store),
find(s1, s2, N, M - 1,
store)));
return mp.get(temp); }
}
// Driver Code
public static void main(String args[]) {
String s1, s2;
s1 = "aabbcc";
s2 = "aabc";
int store = 0;
System.out.println(find(s1, s2, s1.length(), s2.length(), store));
}
}
// This code is contributed by Pushpesh Raj
Python3
# Python3 program to implement the approach
# Map for memoization
mp = {}
# Function to find lcs
# with no repeating character
def find(s1,s2,N,M,store):
if (N == 0 or M == 0):
return 0
temp = str(N) + '#' + str(M) + '#' + str(store)
if(temp in mp):
return mp[temp]
# If the characters are same
if (s1[N - 1] == s2[M - 1] and ((store >> (ord(s1[N - 1]) - ord('a'))) & 1)== 0):
store = (store | (1 << (ord(s1[N - 1]) - ord('a'))))
mp[temp] = 1 + find(s1, s2, N - 1,M - 1, store)
return mp[temp]
# if the characters are different
else:
mp[temp] = max(find(s1, s2, N - 1,M, store),find(s1, s2, N, M - 1,store))
return mp[temp]
# Driver code
s1 = "aabbcc"
s2 = "aabc"
store = 0
print(find(s1, s2, len(s1),len(s2), store))
# This code is contributed by shinjanpatra
C#
// C# program to implement the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// Map for memoization
static Dictionary<string, int> mp
= new Dictionary<string, int>();
// Function to find lcs
// with no repeating character
static int find(string s1, string s2, int N, int M,
long store)
{
if (N == 0 || M == 0)
return 0;
string temp = N.ToString() + '#' + M.ToString()
+ '#' + store.ToString();
if (mp.ContainsKey(temp)) {
return mp[temp];
}
// If the characters are same
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1[N - 1] - 'a')) & 1) == 0) {
store = (store | (1 << (s1[N - 1] - 'a')));
return mp[temp]
= 1 + find(s1, s2, N - 1, M - 1, store);
}
// if the characters are different
else
return mp[temp]
= Math.Max(find(s1, s2, N - 1, M, store),
find(s1, s2, N, M - 1, store));
}
// Driver code
public static void Main()
{
string s1 = "aabbcc";
string s2 = "aabc";
long store = 0;
Console.Write(
find(s1, s2, s1.Length, s2.Length, store));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to implement the approach
// Map for memoization
let mp = new Map();
// Function to find lcs
// with no repeating character
function find(s1, s2, N, M,store)
{
if (N == 0 || M == 0)
return 0;
let temp = N.toString() + '#'
+ M.toString() + '#'
+ store.toString();
if (mp.has(temp))
return mp.get(temp);
// If the characters are same
if (s1[N - 1] == s2[M - 1]
&& ((store >> (s1.charCodeAt(N - 1) - 97))
& 1)
== 0) {
store = (store | (1 << (s1.charCodeAt(N - 1) - 97)));
mp.set(temp,1 + find(s1, s2, N - 1,M - 1, store));
return mp.get(temp);
}
// if the characters are different
else{
mp.set(temp,Math.max(find(s1, s2, N - 1,M, store),find(s1, s2, N, M - 1,store)));
return mp.get(temp);
}
}
// Driver code
let s1 = "aabbcc";
let s2 = "aabc";
let store = 0;
document.write(find(s1, s2, s1.length, s2.length, store));
// code is contributed by shinjanpatra
</script>
Producción
3
Complejidad de tiempo: O(N * M) donde N es el tamaño de s1 y M es el tamaño de s2
Espacio auxiliar: O(N * M)