Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

Its not clear from your examples and description what is the real problem. How is the answer to your first example Yes, it should be No since you can't words "ab":2. Something is missing here or I am not following your question/description.

Comment hidden because of low score. Click to expand.
1
of 1 vote

DP solution similar to Word break maintaining Map with count

``````/*
* Break string into the word provided by given hashmap
* Ex:1
*      HashMap: {"abc":3, "ab":2, "abca":1}
*      Word: abcabcabca
* Output: true
* */

#include <bits/stdc++.h>
using namespace std;
string s;
map<string, int> HashMap;

int DP[11111];
bool solve(int id)
{
if(id >= s.size()) {
return true;
}

if(DP[id] != -1) {
return DP[id];
}

int ans = false;
for(int i = 1; i <= s.size() - id; i++) {
string temp = s.substr(id, i);
// If found
if(HashMap.find(temp) != HashMap.end()) {
if(HashMap[temp] != 0) {
HashMap[temp]--;
ans = ans | solve(id + i);
HashMap[temp]++;
}
}
if(ans == true) {
DP[id] = ans;
return DP[id];
}
}
return DP[id] = ans;
}

int main()
{
cin >> s;
memset(DP, -1, sizeof DP);
// Create HashMap of size N
int N;
cin >> N;
for(int i = 0; i < N; i++) {
string t;
int cnt;
cin >> t >> cnt;
HashMap[t] = cnt;
}
cout << solve(0);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved this problem in varies ways [ we can also use trie to solve this ]

``````public class BuildStringWordsInDictionary {

public static void main(String args[]) {
test1();
test2();
test3();
test4();
test5();

}

//false
private static void test5() {
String s = "abcabab";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 1);

System.out.println("\nGiven String : " + s + " Expected output :" + false);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));

}

//true
private static void test4() {
String s = "abcabab";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);

System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}

//false
private static void test3() {
String s = "abcx";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);
wordCount.put("abca", 1);

System.out.println("\nGiven String : " + s + " Expected output :" + false);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}

//true
private static void test1() {

String s = "abcabcabcabca";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 2);
wordCount.put("abca", 1);

System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
}

//true
private static void test2() {

String s = "abcabcaabbc";
HashMap<String, Integer> wordCount = new HashMap<>();
wordCount.put("abc", 3);
wordCount.put("ab", 1);
wordCount.put("abca", 1);

System.out.println("\nGiven String : " + s + " Expected output :" + true);
System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));

}

}

/**
* NOTE: Not working
*/
class SolutionBFSByStringWords {

public static boolean canBreak(String str, Map<String, Integer> wordCount) {

if (str.isEmpty())
return true;

return canBreakBFS(str, wordCount);

}

private static boolean canBreakBFS(String str, Map<String, Integer> wordCount) {

int n = str.length();
final Queue<Integer> queue = new LinkedList<>();

final Map<String, Integer> visited = new HashMap<>();

queue.offer(0);

while (!queue.isEmpty()) {

int start = queue.poll();

for (int i = start ; i < str.length(); i++) {

//Try this word : forward ->
String temp = str.substring(start, i + 1);

if (!visited.containsKey(temp))
visited.put(temp, 0);

//Check is this possible ?
if (wordCount.containsKey(temp) && wordCount.get(temp) > visited.get(temp)) {

visited.put(temp, visited.get(temp) + 1);

//if possible,the remove this string and recurse for rest of the string;
wordCount.put(temp, wordCount.get(temp) - 1);

//recurse for rest of the string;
queue.offer(i);

if (i == str.length())
return true;

}
}

}

return false;
}
}

/**
* This solution won't handle the cases when you can remove the word in-between and form a new workd by ends
* Example:
* s = "abcabcaabbc";
* {"abc": 3, "ab": 1, "abca": 1}
* <p>
* Your code produce False where it is possible ;
* abcabcaabbc -> aabbc [remove two "abc"] {"abc": 1, "ab": 1, "abca": 1}
* aabbc -> abc [remove one "ab" ] {"abc": 1, "ab": 0, "abca": 1} [**** This is not supported ***]
* abc -> "" [ remove one "abc" ] {"abc": 0, "ab": 1, "abca": 1}
*/
class SolutionDFSByStringWords {

/**
* DFS 1:
* By keeping the index of recursion
*
* @param str
* @param wordCount
* @return
*/
public static boolean canBreak(String str, Map<String, Integer> wordCount) {

if (str.isEmpty())
return true;

return canBreakRec(str, wordCount, 0);

}

/**
* Keep taking a sub-string from given string specified by "start" index and keep checking does this is possible break
* which leads to a solution
*
* @param str
* @param wordCount
* @param start
* @return
*/
private static boolean canBreakRec(String str, Map<String, Integer> wordCount, int start) {

//If we have remove all the chars, then success
if (start == str.length())
return true;

for (int i = start; i < str.length(); i++) {

//Try this word : forward ->
String temp = str.substring(start, i + 1);

//Check is this possible ?
if (wordCount.getOrDefault(temp, -1) > 0) {

//if possible,the remove this string and recurse for rest of the string;
wordCount.put(temp, wordCount.get(temp) - 1);

//recurse for rest of the string;
if (canBreakRec(str, wordCount, i + 1)) {
return true;
}
//Couldn't find the solution, backtrack
wordCount.put(temp, wordCount.get(temp) + 1);

}

}

return false;
}

/**
* DFS 2
* By breaking string into sub-strings
*
* @param word
* @param map
* @return
*/

public static boolean wordBreak(String word, Map<String, Integer> map) {
int len = word.length();
if (len <= 0) return true;
for (int i = 1; i < len + 1; i++) {
String a = word.substring(0, i);
Integer I = map.get(a);
if (I == null || I <= 0)
continue;

map.put(a, I - 1);

if (i <= len && wordBreak(word.substring(i, len), map))
return true;

map.put(a, I);
}
return false;
}
}

class SolutionDFSByMapWords {

public static boolean canBreak(String str, Map<String, Integer> wordCount) {

if (str.isEmpty())
return true;

return canBreakRec(str, wordCount);

}

/**
* DFS the tree.
* check using current count in map of a word, does string can be broken ?
* if yes, then decrease the number of counts and recurse for further. Try all
*
* @param str
* @param wordCount
* @return
*/
private static boolean canBreakRec(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;

/**
* find all the keys present in str and remove them as many times as said
*/
for (String key : wordCount.keySet()) {

int count = wordCount.get(key);

//Can we still use this word from dict?
if (count > 0) {

int oldCount = count;

String oldString = str;

//Find and remove the occurrence
while (str.contains(key) && count > 0) {
str = str.replaceFirst(key, "");
count--;
}

//if we tried to remove but no occurrence found for given key in string, then continue to next word in map
if (count == wordCount.get(key))
continue;
else {

//decrease the count of occurrence
wordCount.put(key, count);

//Recurse
if (canBreakRec(str, wordCount)) {
return true;
}

//Put back: Backtrack
str = oldString;
wordCount.put(key, oldCount);

}

}

}
return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``test and show how is this working``

Comment hidden because of low score. Click to expand.
0
of 0 vote

asdf

Comment hidden because of low score. Click to expand.
0
of 0 vote

Your second example is incorrect (abcabab : ['abc', 'ab', 'ab']). You did
not mention that not all words/occurencies need to be exhausted.

``````def SplitSubstring(s, n, word_fr, curr_split):
if n == len(s):
print("%s : %s" % (s, curr_split))
return
for i in range(n, len(s)):
ss = s[n:i+1]
if ss in word_fr and word_fr[ss] > 0:
word_fr[ss] -= 1
curr_split.append(ss)
SplitSubstring(s, i + 1, word_fr, curr_split)
curr_split.pop()
word_fr[ss] += 1

word_fr = {"abc":3, "ab":2, "abca":1}
SplitSubstring("abcabcabcabca", 0, word_fr, [])
SplitSubstring("abcx", 0, word_fr, [])

word_fr =  {"abc":3, "ab":2}
SplitSubstring("abcabab", 0, word_fr, [])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;

public class BreakWord{
static boolean ans = false;
public static void main(String[] args){
Map<String, Integer> map = new HashMap<>();
//map.put("abc", 3);
//map.put("ab", 2);
//map.put("abca", 1);
map.put("abc", 3);
map.put("ab", 2);
String str = "abcabcabcabca";
//String str = "abcabab";

Set<String> set = new HashSet<>();
for(String s : map.keySet()){
}

dfs(map, set, str, 0);
System.out.println(ans);
}

public static void  dfs(Map<String, Integer> map, Set<String> set, String str, int start){
if(start == str.length()){
ans = true;
return;
}
for(int i=start; i<str.length(); i++){
String ss = str.substring(start, i+1);
if(!set.contains(ss))
continue;
if(map.get(ss) == 0){
continue;
}
map.put(ss, map.get(ss)-1);
dfs(map, set, str, i+1);
map.put(ss, map.get(ss)+1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

This (the above java code) fails for the case "abcabab". the code is really simple, and I like it, but it doesn't catch this case. although I admit the question is poorly worded.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this is optimal, but here is a DP solution that requires what is likely a significant amount of space.

DP Solution:

T[i,j,k,l] = True if there is a partition of S[i..j] using the i^th substring at most k times.

If T[i,j,k,l] is true, then some substring must be a prefix of S[i..j], so just check all possible prefixes.

Fill in table in increasing order of abs(i-j), and increasing order of k and l.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution:

``````#include <iostream>
using namespace std;

struct dict
{
string w;
int c;
};

// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
if (str.length()==0)
return true;
else
for (int wo=0;wo<3;wo++)
{
int d_length=d[wo].w.length();
//cout<<str.substr(0,d_length)<<endl;

if (str.substr(0,d_length) == d[wo].w )
{

//d[wo].c--;
if (findwords(str.substr(d_length,str.length()),d,words))
{
// cout<<d[wo].w<<" ";

d[wo].c--;
if (d[wo].c>=0)
{
words=d[wo].w+" "+words;
return true;
}
}
//d[wo].c++;
}
}
return false;
}

int main() {

dict d[3];

d[0].w="abc";
d[1].w="ab";
d[2].w="abca";

d[0].c=2;
d[1].c=2;
d[2].c=1;
string words;

if (findwords("abcaababcab",d,words))
cout<<"True"<< " "<<words<<endl;
else
cout << "No Words Found"<<endl;

//cout<<words<<endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Solution

``````#include <iostream>
using namespace std;

struct dict
{
string w;
int c;
};

// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
if (str.length()==0)
return true;
else
for (int wo=0;wo<3;wo++)
{
int d_length=d[wo].w.length();
//cout<<str.substr(0,d_length)<<endl;

if (str.substr(0,d_length) == d[wo].w )
{

//d[wo].c--;
if (findwords(str.substr(d_length,str.length()),d,words))
{
// cout<<d[wo].w<<" ";

d[wo].c--;
if (d[wo].c>=0)
{
words=d[wo].w+" "+words;
return true;
}
}
//d[wo].c++;
}
}
return false;
}

int main() {

dict d[3];

d[0].w="abc";
d[1].w="ab";
d[2].w="abca";

d[0].c=2;
d[1].c=2;
d[2].c=1;
string words;

if (findwords("abcaababcab",d,words))
cout<<"True"<< " "<<words<<endl;
else
cout << "No Words Found"<<endl;

//cout<<words<<endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You could flatten out the hash map and then generate the power set. Then map each element in the power set to an array of permutations of the original array that are then joined together as strings.

Then collect all of these generated strings, this is your solution space. Check if the input exists in the space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

here's my VS 2019 C# entry

``````static List<string> l = new List<string>( );
static Dictionary<string,int> dict = new Dictionary<string, int>( );

static void FindString( string szFind, int szFindLen, List<string> szRemainingWords, ref bool bFound, ref string szOut )
{
if( szFind == "" )
{
bFound = true;
return;
}

string szOutOriginal = szOut;

for( int i = 0 ; i < szRemainingWords.Count ; i++ )
{
string s = szRemainingWords[i];
if ( szFind.StartsWith( s ) )
{
szOut += s + " ";
int len = s.Length;

szRemainingWords [i] = "*" + szRemainingWords [i];
FindString( szFind.Substring( len ), szFindLen - len, szRemainingWords, ref bFound, ref szOut );
szRemainingWords [i] = szRemainingWords [i].Substring( 1 );

if ( bFound )
{
break;
}
}
}

if( !bFound )
{
szOut = szOutOriginal;
}
}

static bool DoesWordAppearNTimes( string szWholeString, string szFindWord, int n )
{
int offset = 0;
while ( n > 0 )
{
int i = szWholeString.Substring( offset ).IndexOf( szFindWord );
if ( i == -1 )
{
return false;
}
offset = i;
n--;
}
return true;
}

static void Main( string [] args )
{

bool bFound = false;
string szOut = "";
string szFind = "abcabab";

FindString( szFind, szFind.Length, l, ref bFound, ref szOut);
if ( bFound )
{
foreach ( KeyValuePair<string, int> kvp in dict )
{
if( !DoesWordAppearNTimes( szFind, kvp.Key, kvp.Value ) )
{
bFound = false;
break;
}
}
}
Console.WriteLine( "Find = " + szFind + ", found = " + bFound.ToString( ) + ", string = " + szOut );

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool break1(string& s, std::unordered_map<string, int>& countMap) {
int size = s.size();
std::unordered_map<int, vector<vector<string>>> table;

for (int i = 0; i < size; ++i) {

vector<vector<string>> entry;

for (int j = 0; j <= i; ++j) {

//"abcabcabcabababca"

string str1 = s.substr(0, j);

string str2 = s.substr(j, i - j + 1);

if (j == 0) {

if (countMap.find(str2) != countMap.end()) {
vector<string> vec1;
vec1.push_back(str2);
entry.push_back(vec1);
}

}
else {
if (table[j-1].size() > 0 && countMap.find(str2) != countMap.end()) {
for (auto iter = table[j-1].begin(); iter != table[j-1].end(); ++iter) {
auto vec = *iter;
vec.push_back(str2);
entry.push_back(vec);
}

}
}
//            else {
//                if (countMap.find(str2) != countMap.end()) {
//                    vector<string> vec;
//                    vec.push_back(str2);
//                    entry.push_back(vec);
//                }
//            }
}// for (int j = 0; j <= i; ++j)

table[i] = entry;
}// for (int i = 0; i < size; ++i)

for (auto iter = table.begin(); iter != table.end(); ++iter) {
int i = iter->first;
vector<vector<string>> entry = iter->second;
if (entry.size() > 0) {
std::cout << "index is " << i << "\n";
}

for (auto iter1 = entry.begin(); iter1 != entry.end(); ++iter1) {
for (auto iter2 = (*iter1).begin(); iter2 != (*iter1).end(); ++iter2) {
std::cout << *iter2 << "\t";
}

std::cout << "\n";
}

std::cout << "\n";
}

vector<vector<string>> solutions = table[size - 1];

while (solutions.size() > 0) {
auto copyCountMap = countMap;
vector<string> vec = solutions.back();
solutions.pop_back();

for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
copyCountMap[*iter]--;
if (copyCountMap[*iter] == 0) copyCountMap.erase(*iter);
}

if (copyCountMap.size() == 0) return true;

}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````const myFunc = (str, strMap) => {

let origStr = str;
let outputArray = [];
let mapArray = [];

// create subArrays of hashmaps

for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}

// order arrays by subArray length

const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});

// check for matches

for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}

// format output

if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: Yes;[\${outputArray}]`;
} else {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: No`;
}
}

let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````const myFunc = (str, strMap) => {

let origStr = str;
let outputArray = [];
let mapArray = [];

// create subArrays of hashmaps

for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}

// order arrays by subArray length

const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});

// check for matches

for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}

// format output

if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: Yes;[\${outputArray}]`;
} else {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: No`;
}
}

let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````const myFunc = (str, strMap) => {

let origStr = str;
let outputArray = [];
let mapArray = [];

// create subArrays of hashmaps

for (let key in strMap) {
let count = strMap[key];
let tokenArray = [...Array(count)].map((_, i) => key);
mapArray.push(tokenArray);
}

// order arrays by subArray length

const sortedArrays = mapArray.sort((a, b) => {
return b.length - a.length;
});

// check for matches

for(let hashArray of sortedArrays) {
let pattern = hashArray.join('');
if (str.includes(pattern)) {
outputArray = outputArray.concat(hashArray);
str = str.replace(pattern, '');
}
}

// format output

if (str.length ===0 && outputArray.length > 0) {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: Yes;[\${outputArray}]`;
} else {
return `
HashMap -> \${JSON.stringify(strMap)}
String: \${origStr}
output: No`;
}
}

let string = 'abcabcabcabca'
let stringMap = {
'abc': 3,
'ab': 2,
'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution

It has a complexity of O(H * CK) where H is the number of the items in the given hash key and CK is the maximum number of words frequency across all the hashes

``````let inputString = 'abcabcabcabca';
var validationHash = { "abc": 3, "ab": 2, "abca": 1 };

const breakTheStringIntoWords = (inputString, validationHash) => {
var replacer = '';
var words = [], tempWords = [], ii;

Object.keys(validationHash).map(compareKey => {
replacer = '';
tempWords = [];

for (ii = 0; ii < validationHash[compareKey]; ii++) {
tempWords.push(compareKey);
replacer += compareKey;
}

if (inputString.indexOf(replacer) > -1) {
inputString = inputString.replace(replacer, '');
words = words.concat(tempWords);
tempWords = [];
}
});

if (inputString.trim() === '') {
return words;
} else {
return [];
}
};

const returnedWords = breakTheStringIntoWords(inputString, validationHash);

if(returnedWords.length > 0){
console.log('Yes;', returnedWords);
} else {
console.log('No');
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def wordcheck(str,hash):

result = {}
for k,v in hash.items():
x = len(k)
word_count=0
for i in range(len(str)):
if str[i:x+i] == k:

word_count +=1
if word_count == v:
result[k] = word_count
if result == hash:
return True
else:
return False

hash = {'abc':3,'ab':2,'abca':1}
str = 'abcabcabcabca'

print(wordcheck(str,hash))

hash = {"abc":3, "ab":2}
str= 'abcabab'
print(wordcheck(str,hash))

hash = {"abc":3, "ab":2, "abca":1}
str= 'abcx'
print(wordcheck(str,hash))``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []

function findLongestPrefix(str, index, dict, maxPrefixLen) {

var dictCopy = Object.assign({}, dict);

if (index >= str.length)
return [];

for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);

if (dictCopy[candidate]) {
dictCopy[candidate]--;

try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}

throw error('E_INVALID_CHARS')

}

function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}

try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []

function findLongestPrefix(str, index, dict, maxPrefixLen) {

var dictCopy = Object.assign({}, dict);

if (index >= str.length)
return [];

for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);

if (dictCopy[candidate]) {
dictCopy[candidate]--;

try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}

throw error('E_INVALID_CHARS')

}

function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}

try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []

function findLongestPrefix(str, index, dict, maxPrefixLen) {

var dictCopy = Object.assign({}, dict);

if (index >= str.length)
return [];

for (var i = maxPrefixLen; i > 0; i--) {
var candidate = str.substr(index, i);

if (dictCopy[candidate]) {
dictCopy[candidate]--;

try {
var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
return [candidate].concat(rest);
} catch(err) {
dictCopy[candidate]++;
}
}
}

throw error('E_INVALID_CHARS')

}

function breakWords(str, dict) {
// Get the max lengths of keys
var keys = Object.keys(dict);
var maxPrefixLen = 1;
for (var i = 0; i < keys.length; i++ ) {
if (keys[i].length > maxPrefixLen) {
maxPrefixLen = keys[i].length;
}
}

try {
return findLongestPrefix(str, 0, dict, maxPrefixLen)
} catch(error) {
return []
}
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.