Un tableau de N mots est donné. Chaque mot est composé de minuscules («a» - «z»). Notre objectif est de concaténer les mots de manière à obtenir un seul mot avec la sous-chaîne la plus longue possible composée d'une lettre particulière. Trouvez la longueur d'une telle sous-chaîne.
Exemples:
Étant donné N = 3 et les mots = ['aabb', 'aaaa', 'bbab'], votre fonction doit renvoyer 6. L'une des meilleures concaténations est les mots [1] + mots [0] + mots [2] = 'aaaaaabbbbab ». La sous-chaîne la plus longue est composée de la lettre «a» et sa longueur est de 6.
Étant donné N = 3 et les mots = ['xxbxx', 'xbx', 'x'], votre fonction devrait renvoyer 4. L'une des meilleures concaténations est les mots [0] + mots [2] + mots [1] = 'xxbxxxxbx ». La sous-chaîne la plus longue est composée de la lettre «x» et sa longueur est de 4.
Je sais que je ne devrais pas publier la réponse, mais cela pourrait aider quelqu'un qui recherche une solution optimale.
class DailyCodingProblem4 {
public static void main(String args[]) {
String[] arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String[] arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String[] arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
4 Réponses :
Pour chaque lettre, vous devez savoir:
Étant donné que chaque mot entre dans au plus 2 de ces groupes, déterminés par les lettres avec lesquelles il commence et se termine, vous pouvez tout comprendre en temps O (N).
merci pour la logique. Je comprends ce que vous essayez ici. Je vais l'essayer et voir. Je devrais maintenir un tableau pour chaque caractère, car nous devons trouver la sous-chaîne maximale s'il y a un caractère.
Une solution possible est de générer toutes les combinaisons possibles et de trouver la plus grande longueur de sous-chaîne, contenant les mêmes caractères;
import java.util.*;
class Test{
static int max = 0; // variable : holds largest length of substring
public static void main(String[] args) {
String [] array = {"aabb", "aaaa", "bbab"};
getLengthOfLongestSubString(array, 0, array.length-1);
System.out.println(max);
}
static void getLengthOfLongestSubString(String [] array, int l, int r){
if(l==r){
String s = "";
for(int i=0; i<array.length; i++){
s += array[i];
}
int count = 1;
String temp = "";
// System.out.println(s);
for(int i = 1; i<s.length(); i++){
if(s.charAt(i-1) == s.charAt(i)){
temp += s.charAt(i-1);
count++;
}else{
if(count > max){
// System.out.println(temp);
max = count;
}
count = 1;
temp = "";
}
}
}else{
for(int i=l; i<=r; i++){
array = swap(array, l, i);
getLengthOfLongestSubString(array, l+1, r);
array = swap(array, l, i);
}
}
}
static String [] swap(String [] array, int i, int j){
String temp = array[i];
array[i] = array[j];
array[j] = temp;
return array;
}
}
Pour une lettre particulière, la sous-chaîne la plus longue possible peut être formée de deux manières
Il peut se présenter comme le suffixe d'un mot + tous les mots qui se composent entièrement de cette lettre + préfixe d'un autre mot. Par exemple 'abxaa' + 'aaa' + 'a' + 'abvdf' donc ici la longueur de la sous-chaîne de 'a' est 7 . Pour obtenir la plus longue sous-chaîne de ce type, vous devez
i) Obtenez le suffixe le plus long de ce caractère (n'incluez pas les mots où seul ce mot apparaît, nous les utiliserons à l'étape suivante). Par exemple, dans ['aabb','aaaa','bbab'] et la lettre 'a' ce sera 0 car il n'y a pas de mot où la sous-chaîne de 'a' est un préfixe strict.
ii) Obtenez la longueur totale de tous les mots où seule cette lettre est présente. Dans l'exemple, c'est 4 (en 'aaaa' ).
iii) Effectuez l'étape i) mais maintenant pour les préfixes stricts. Pour l'exemple, ce sera 2 (dans 'aabb' )
iv) Additionnez les valeurs des trois étapes ci-dessus. Vous obtenez 0 + 4 + 2 = 6 pour l'exemple avec la lettre 'a' .
La sous-chaîne peut être complètement à l'intérieur d'un mot. Trouvez la longueur maximale de ces cas. Pour notre exemple, c'est 1 dans ( 'bbab' ).
En prenant le maximum de ces deux solutions possibles, vous obtenez la sous-chaîne de longueur maximale pour cette lettre. Maintenant, effectuez simplement ceci pour les 26 lettres et prenez le maximum. Je vous laisse pour la mise en œuvre, mais faites-moi savoir si vous rencontrez un problème. La complexité temporelle est O(Total length of all words) .
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <iterator>
using namespace std;
int parse_map(multimap<int,tuple<char,bool,int>>& record, char& c, multimap<int,tuple<char,bool,int>> :: iterator &mIt)
{
int idx = -1;
int retval = 0;
bool notFound = false;
if((get<bool>(mIt->second)) && mIt->first > 0)
{
retval +=mIt->first;
if(mIt != record.begin())
--mIt;
else
return retval;
for(;mIt->first > 0; mIt-- )
{
if(get<char>(mIt->second) == c)
{
retval += mIt->first;
break;
}
if(mIt == record.begin())
break;
}
notFound = true;
}
else if(mIt->first > 0)
{
retval += mIt->first;
idx = get<int>(mIt->second);
for(;mIt->first > 0; mIt--)
{
if((get<bool>(mIt->second)) && (get<char>(mIt->second) == c))
{
retval += mIt->first;
break;
}
}
notFound = true;
}
if(mIt->first > 0 || notFound)
mIt = record.begin();
else
{
retval -= mIt->first;
auto mIte = record.end();
--mIte;
while((get<char>(mIte->second) != c) && (mIte->first > 0))
{
--mIte;
}
if(mIte->first > 0)
{
if(get<int>(mIte->second) != get<int>(mIt->second))
{
retval = parse_map(record,c,mIte);
}
else
{
--mIte;
if(mIte->first > 0)
retval = parse_map(record,c,mIte);
}
}
return retval;
}
for(;mIt->first < 0; mIt++)
{
//Prefix scenario
if ((get<int>(mIt->second) != idx) && (get<char>(mIt->second) == c))
{
retval -= mIt->first;
break;
}
}
return retval;
}
int solution(vector<string> &A)
{
int max_substring;
max_substring = 0;
int substring_idx = -1;
multimap<int,tuple<char,bool,int>> record;
for(int i = 0; i < A.size(); i++)
{
int count;
count = 1;
// 2 Corner cases, 1 empty and the other only has 1 char
if(A[i].size() == 0)
continue;
else if(A[i].size() == 1)
{
tuple<char,bool,int> p = make_tuple(A[i].front(), true,i);
multimap<int,tuple<char,bool,int>> :: iterator mIta;
for(mIta = record.begin(); mIta != record.end(); mIta++)
{
if ((get<char>(mIta->second) == get<char>(p)) && get<bool>(mIta->second))
break;
}
if(mIta != record.end())
{
record.insert({count + mIta->first,p});
record.erase(mIta);
}
else
{
record.insert({count,p});
}
continue;
}
for(int j = 1; j < A[i].size(); j++)
{
if (A[i][j] == A[i].front())
{
count ++;
}
else
{
for(int g = A[i].size() -2; g > j; g--)
{
char temp = A[i][g];
int len = 1;
while((temp == A[i][g-1]) && (g>j))
{
len ++;
g--;
}
max_substring = max(max_substring,len);
}
break;
}
}
multimap<int,tuple<char,bool,int>> :: iterator mIta;
if (A[i].size() == count)
{
tuple<char,bool,int> p = make_tuple(A[i].front(), true,i);
for(mIta = record.begin(); mIta != record.end(); mIta++)
{
if ((get<char>(mIta->second) == get<char>(p)) && get<bool>(mIta->second))
break;
}
if(mIta != record.end())
{
record.insert({count + mIta->first,p});
record.erase(mIta);
}
else
{
record.insert({count,p});
}
continue;
}
tuple<char,bool,int> p = make_tuple(A[i].front(), false,i);
for(mIta = record.begin(); mIta != record.end(); mIta ++)
if((mIta->first) == count)
break;
if(mIta != record.end())
{ for(; mIta != record.upper_bound(count); mIta++)
{
if (get<char>(mIta->second) == get<char>(p))
record.erase(mIta);
record.insert({count,p});
}
}
else
record.insert({count,p});
count = -1;
for(int j = (A[i].size()-2); j >= 0; j--)
{
if(A[i][j] == A[i].back())
{
count --;
}
else break;
}
p = make_tuple(A[i].back(), false,i);
for(mIta = record.begin(); mIta != record.end(); mIta ++)
if((mIta->first) == count)
break;
if(mIta != record.end())
{ for(; mIta != record.upper_bound(count); mIta++)
{
if (get<char>(mIta->second) == get<char>(p))
record.erase(mIta);
record.insert({count,p});
}
}
else
record.insert({count,p});
}
//Tidying up spaghetti code #new implementation in helper for tidyness.
int retval;
retval = 0;
auto mItb = record.begin();
if(record.size() == 1)
return mItb->first;
auto mIte = record.end();
--mIte;
int idx = mItb->first;
// Chk postfix
if(idx < 0)
{
while(mItb->first == idx)
{
char c = get<char>(mItb->second);
retval = max(parse_map(record, c, mItb),retval);
++mItb;
}
}
// Chk prefix
mIte = record.end();
mIte--;
idx = mIte->first;
while(mIte->first == idx)
{
char c = get<char>(mIte->second);
retval = max(parse_map(record, c, mIte),retval);
--mIte;
}
return max(retval,max_substring);
}
int main()
{
vector<string> A{"aabb", "aaaa", "bbab"};
vector<string> B{"xxbxx", "xbx", "x"};
vector<string> C{"dd", "bb", "cc", "dd"};
vector<string> D{"abbba"};
vector<string> E{"bb", "b", "aaa", "ab", "bba"};
vector<string> F{"aaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaa"};
cout<<"Expected_6 \t"<<"got \t"<<solution(A)<<endl;
cout<<"Expected_4 \t"<<"got \t"<<solution(B)<<endl;
cout<<"Expected_4 \t"<<"got \t"<<solution(C)<<endl;
cout<<"Expected_3 \t"<<"got \t"<<solution(D)<<endl;
cout<<"Expected_6 \t"<<"got \t"<<solution(E)<<endl;
cout<<"Expected_24 \t"<<"got \t"<<solution(F)<<endl;
}
I used a multimap with negative keys for this.
Suffix is negative, postfix is positive.
A counter is used to track the longest string reside in the middle without concatenation while populating the map.
The multimap auto sorted the biggest number as the most negative and the most positive number
If the string only consist of one single char, it is concatenated while the map was being populated as a joker card on a deck.
The field to the map is [occurrence]
Occurrence is explained above, char is the letter involved, bool is whether it is a wildcard joker that will be added no matter what. int to prevent recount of same string(suffix and prefix on the same string).
2 while loop. 1 for postfix bias, 1 for prefix bias. return max of them
In the recursive function, chk if bool, if so we keep going until we find a next biggest prefix that will maximize the concatenation.
In the recursive function, if the initial case isn't bool, we keep going until we find bool the joker, (See 4. to see why we don't need to travel further)
Add the postfix that corresponds if any
This is where postfix bias mattered. (7~9) are prefix bias. That means we might skip the largest postfix. But if the postfix is sufficiently large, there could be a possibility that the postfix + whatever small prefix and joker can result in the longest string. Hence the initial branch (See 6.) to compare the max of bias.
@Elletlar - En fait, ce n'est pas non plus un service de correction de code.
@Elletlar J'ai essayé de trouver une solution depuis 4 jours maintenant. La seule solution que je pourrais trouver est la force brute. Ce problème n'est pas aussi simple qu'il y paraît.