educative.io

Optimized version following solution of Problem Challenge 1

Courses
,
#1

Following is an optiized solution in c++ following solution of Problem Challenge 1:

using namespace std;

#include
#include
#include <unordered_map>
#include

class WordConcatenation {
public:
static vector findWordConcatenation(const string &str, const vector &words) {
vector resultIndices;

if(str.length() == 0 || words.size() == 0) {
  return resultIndices;
}
unordered_map<string,int> wordFreq;
for( auto w: words) {
  wordFreq[w]++;
}

int wordCount = words.size();
int wordLen = words[0].length();

int wStart = 0;
int matched = 0;

for(int wEnd = 0; wEnd < str.length(); wEnd += wordLen) {
  string word = str.substr(wEnd,wordLen);
  
  if(wordFreq.find(word) != wordFreq.end()) {
    wordFreq[word]--;
    if(wordFreq[word]==0) {
      matched++;
    }
  } 


  if(matched == wordFreq.size()) {
    resultIndices.push_back(wStart);
  }

  if(wEnd + wordLen >= wordCount * wordLen - 1) {
    string wordStart = str.substr(wStart, wordLen);
    if(wordFreq[wordStart] == 0) {
      matched--;
    }
    wordFreq[wordStart]++;

    wStart += wordLen;
  }
}



return resultIndices;

}
};

int main(int argc, char *argv[]) {
vector result =
WordConcatenation::findWordConcatenation(“catfoxcat”, vector{“cat”, “fox”});
for (auto num : result) {
cout << num << " ";
}
cout << endl;

result = WordConcatenation::findWordConcatenation(“catcatfoxfox”, vector{“cat”, “fox”});
for (auto num : result) {
cout << num << " ";
}
cout << endl;
}

#2

You can’t use the pace as wordLength because the input string maynot be a concatenation of words from the input words. It can have other letters in it.

Think about one example like this: string: “catafoxcatfox” words: [“cat”, “fox”]. If using pace as wordLength, string is separated into [“cat”, “afo”, “xca”, “tfo”, “x”] which will return no answer. But actually it has answer [4].

#3

Another solution (in JS) … not really using sliding window:

const find_permutation = function(str, pattern) {

const pArr = pattern.split(’’), pLength = pArr.length, sArr = str.split(’’);
let substringAvailable = false, matchCount = 0;
let charMap = {}, matchCharMap = {};

for(let i=0; i< pLength; i++) {
let c = pattern[i];
if(!charMap[c]) {
charMap[c] = 0;
}
charMap++;
}

for(let windowEnd=0; windowEnd<sArr.length; windowEnd++) {

let rightChar = sArr[windowEnd];

if(!pArr.includes(rightChar)){ 
    matchCount = 0;
} else {
    if( !matchCharMap[rightChar]){
      matchCharMap[rightChar] = 1
    } 
    matchCharMap[rightChar] +=1;

    if(matchCharMap[rightChar] > charMap[rightChar]) {
      matchCount = 0;
    } else {
      matchCount++;
    }
}

if(matchCount === pLength) {
  substringAvailable = true;
}

}

return substringAvailable;

};