So, the solution provided is complex and I don’t think it follows the sliding window technique. Besides that, the complexity is difficult to understand too.
I have attempted to solve this problem in O(n) where n is the size of the input string.
I would love to get some comments on it.
private static List<Integer> getStartIndices(String input, String[] words)
{
List<Integer> startingIndices = new ArrayList<>();
Map<String, Integer> wordFrequency = getFrequencyMap(words);
int start = 0, matchedWords = 0;
int nextWordPointer, wordSize = words[0].length(), end = wordSize - 1;
while(end < input.length())
{
nextWordPointer = end + 1 - wordSize;
String nextWord = input.substring(nextWordPointer, end + 1);
if (!wordFrequency.containsKey(nextWord)) {
start += 1;
end += 1;
nextWordPointer += 1;
continue;
}
wordFrequency.put(nextWord, wordFrequency.get(nextWord) - 1);
if (wordFrequency.get(nextWord) == 0)
matchedWords += 1;
if (wordFrequency.get(nextWord) < 0) {
start += wordSize;
wordFrequency.put(nextWord, wordFrequency.get(nextWord) + 1);
}
if (matchedWords == wordFrequency.size()) {
startingIndices.add(start);
String startString = input.substring(start, start + wordSize);
wordFrequency.put(startString, wordFrequency.get(startString) + 1);
start += wordSize;
matchedWords -= 1;
}
end = end + wordSize;
}
return startingIndices;
}
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5223876420173824