Dada una array arr[] que consta de N strings , la tarea es encontrar el producto máximo de la longitud de las strings arr[i] y arr[j] para todos los pares únicos (i, j) , donde las strings arr[i ] y arr[j] no contienen caracteres comunes.
Ejemplos:
Entrada: arr[] = {“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”}
Salida: 16
Explicación: Las strings “abcw” y “xtfn” no tienen caracteres comunes en eso. Por lo tanto, el producto de la longitud de ambas strings = 4 * 4 = 16, que es el máximo entre todos los pares posibles.Entrada: arr[] = {“a”, “aa”, “aaa”, “aaaa”}
Salida: 0
Enfoque ingenuo: la idea es generar todos los pares de strings y usar un mapa para encontrar el carácter común entre ellos, si no hay ningún carácter común entre ellos, entonces use el producto de su longitud para maximizar el resultado.
Siga los pasos a continuación para implementar la idea anterior:
- Genere todos los pares de strings, por ejemplo, s1 y s2 .
- Use un mapa para encontrar el carácter común entre las strings s1 y s2.
- Compruebe si hay algún carácter común entre ellos:
- Si no hay un carácter común entre ellos, utilice el producto de su longitud y maximice el resultado.
- Finalmente, devuelve el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the find the maximum product of the
// length of the strings arr[i] and arr[j] for all unique
// pairs (i, j), where the strings arr[i] and arr[j] contain
// no common characters.
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum product of the length of the
// strings
int maximizeProduct(vector<string>& arr)
{
int n = arr.size();
// This store the maximum product of string's length
int result = 0;
// Iterate to find the 1st string
for (int i = 0; i < n; i++) {
string s1 = arr[i];
int len1 = arr[i].size();
// Map to store the unique character
unordered_map<char, int> unmap;
for (auto c : s1)
unmap++;
// Iterate to find the 2nd string
for (int j = i + 1; j < n; j++) {
string s2 = arr[j];
int len2 = arr[j].size();
bool flag = false;
for (int k = 0; k < s2.size(); k++) {
// Check if the characters of s2 are common
// with s1 characters or not
if (unmap.count(s2[k])) {
flag = true;
break;
}
}
// This verify that there is no common character
// between s1 and s2.
if (flag == false) {
result = max(result, len1 * len2);
}
}
}
return result;
}
// Driver code
int main()
{
vector<string> arr = { "abcw", "baz", "foo",
"bar", "xtfn", "abcdef" };
int result = maximizeProduct(arr);
// Print the output
cout << result;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Java program to find the find the maximum product of the
// length of the strings arr[i] and arr[j] for all unique
// pairs (i, j), where the strings arr[i] and arr[j] contain
// no common characters.
// Function to find the maximum product of the length of the
// strings
static int maximizeProduct(String[] arr)
{
int n = arr.length;
// This store the maximum product of string's length
int result = 0;
// Iterate to find the 1st string
for (int i = 0; i < n; i++) {
String s1 = arr[i];
int len1 = arr[i].length();
// Map to store the unique character
HashMap<Character,Integer> unmap = new HashMap<>();
for (char c : s1.toCharArray()){
if(unmap.containsKey(c)){
unmap.put(c, unmap.get(c)+1);
}
else unmap.put(c,1);
}
// Iterate to find the 2nd string
for (int j = i + 1; j < n; j++) {
String s2 = arr[j];
int len2 = arr[j].length();
boolean flag = false;
for (int k = 0; k < s2.length(); k++) {
// Check if the characters of s2 are common
// with s1 characters or not
if (unmap.containsKey(s2.charAt(k))) {
flag = true;
break;
}
}
// This verify that there is no common character
// between s1 and s2.
if (flag == false) {
result = Math.max(result, len1 * len2);
}
}
}
return result;
}
// Driver Code
public static void main(String args[])
{
String[] arr = { "abcw", "baz", "foo",
"bar", "xtfn", "abcdef" };
int result = maximizeProduct(arr);
// Print the output
System.out.println(result);
}
}
Python3
# Python3 program to find the find the maximum product of the
# length of the strings arr[i] and arr[j] for all unique
# pairs (i, j), where the strings arr[i] and arr[j] contain
# no common characters.
# Function to find the maximum product of the length of the
# strings
def maximizeProduct(arr):
n = len(arr)
# This store the maximum product of string's length
result = 0
# Iterate to find the 1st string
for i in range(n):
s1 = arr[i]
len1 = len(arr[i])
# Map to store the unique character
unmap = {}
for c in s1:
if(c in unmap):
unmap += 1
unmap = 1
# Iterate to find the 2nd string
for j in range(i+1,n):
s2 = arr[j]
len2 = len(arr[j])
flag = False
for k in range(len(s2)):
# Check if the characters of s2 are common
# with s1 characters or not
if (s2[k] in unmap):
flag = True
break
# This verify that there is no common character
# between s1 and s2.
if (flag == False):
result = max(result, len1 * len2)
return result
# Driver code
arr = [ "abcw", "baz", "foo", "bar", "xtfn", "abcdef" ]
result = maximizeProduct(arr)
# Print the output
print(result)
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to find the find the maximum product of the
// length of the strings arr[i] and arr[j] for all unique
// pairs (i, j), where the strings arr[i] and arr[j] contain
// no common characters.
// Function to find the maximum product of the length of the
// strings
function maximizeProduct(arr)
{
let n = arr.length;
// This store the maximum product of string's length
let result = 0;
// Iterate to find the 1st string
for (let i = 0; i < n; i++) {
let s1 = arr[i];
let len1 = arr[i].length;
// Map to store the unique character
let unmap = new Map();
for (let c of s1){
if(unmap.has(c)){
unmap.set(c,unmap.get(c)+1);
}
unmap.set(c,1);
}
// Iterate to find the 2nd string
for (let j = i + 1; j < n; j++) {
let s2 = arr[j];
let len2 = arr[j].length;
let flag = false;
for (let k = 0; k < s2.length; k++) {
// Check if the characters of s2 are common
// with s1 characters or not
if (unmap.has(s2[k])) {
flag = true;
break;
}
}
// This verify that there is no common character
// between s1 and s2.
if (flag == false) {
result = Math.max(result, len1 * len2);
}
}
}
return result;
}
// Driver code
let arr = [ "abcw", "baz", "foo", "bar", "xtfn", "abcdef" ];
let result = maximizeProduct(arr);
// Print the output
document.write(result,"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
16
Complejidad de tiempo: O(N 2 * M), donde M es la longitud máxima de la string .
Espacio Auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por maheswaripiyush9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA