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;
}
}