educative.io

Educative

My solution in O(n) using sliding window. Could anybody take a look at it?

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