educative.io

Educative

Java. Reusing previous template (map+matched) O(n)

The whole point of paying for this course for me is to obtain “RE-USABLE solution patterns”.
I tried to reuse previous solutions and passed within given test cases.

the difference with the previous solution pattern is checking String instead of Character every time.

I think time complexity would be O(n) and space complexity would be O(n).
Please help me if the time and space complexities are wrong.

import java.util.*;

class WordConcatenation {
public static List findWordConcatenation(String str, String[] words) {
List resultIndices = new ArrayList();

int start = 0, matched = 0;
int wordLen = words[0].length(), wordCnt = words.length;

Map<String, Integer> frequency = new HashMap<>();
for (String word : words) frequency.put(word, frequency.getOrDefault(word, 0) + 1);

for (int end = wordLen - 1; end < str.length(); end += wordLen) {
  // check string frequencies in the window
  String wordEnd = str.substring(end - wordLen + 1, end + 1);
  if (frequency.containsKey(wordEnd)) {
    frequency.put(wordEnd, frequency.getOrDefault(wordEnd, 0) - 1);
    if (frequency.get(wordEnd) == 0) matched++;
  }

  // save the window if the window satisfies the requirements
  if (matched == wordCnt) resultIndices.add(start);

  // adjust (reduce) the window size for next iteration
  if (end - start + 1 >= wordCnt * wordLen) {
    String wordStart = str.substring(start, start + wordLen);
    start += wordLen;
    if (frequency.containsKey(wordStart)) {
      if (frequency.get(wordStart) == 0) matched--;
      frequency.put(wordStart, frequency.getOrDefault(wordStart, 0) + 1);
    } 
  }
}
return resultIndices;

}
}

1 Like

Thank you for posting this. I knew there was a way that matches the patterns used in previous sliding window problems.

But, this would not work if the string starts with a few random letters, i.e. “bzcatfox”, String[]{“cat”, “fox”}. this would probably not find a match, since you are making “end” jump wordLen each time.