educative.io

Why this problem is similar to Maximum Sum Subarray of Size?

Courses
,
#1

I don’t understand it. Why this Why this problem is similar to Maximum Sum Subarray of Size question?

Does anyone have any ideas? Thanks!.

#2

I agree, I don’t understand why this problem is even listed in the Sliding Window section :thinking:

1 Like
#3

If you pretend each word is a unique character, you can frame this just like String Anagrams (Problem Challenge 2)

When going through the loop, increment by the length of the words given (they mention they’re all the same length). Instead of checking character by character, get the substring from the original string and check against the words.

2 Likes
#4

I think I have a solution that runs in O(N) time where N is the length of the input str and O(K) space where K is the length of the search array and uses an actual Sliding Window pattern.

Please review. Thanks
public static List findWordConcatenation(String str, String[] words) {
List resultIndices = new ArrayList();

String firstWord = words[0];
int wordLength = firstWord.length();
int wordArrayLength = words.length;

int totalAllowableWords = wordArrayLength * wordLength;

int windowStart = 0;
int firstMatchIndex = 0; 

int matches = 0;

HashMap<String, Integer> wordFreqMap = new HashMap<String, Integer>();

for (String word: words) {
  wordFreqMap.put(word, wordFreqMap.getOrDefault(word, 0) + 1);
}


for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

  if (windowEnd - windowStart + 1 >= wordLength) {
    String contiguousRunningChars = str.substring(windowStart, windowEnd+1);
    if (wordFreqMap.containsKey(contiguousRunningChars)) {

      if (wordFreqMap.get(contiguousRunningChars) == 0) {
        firstMatchIndex = windowEnd - wordLength + 1;
      } else {
        wordFreqMap.put(contiguousRunningChars, wordFreqMap.get(contiguousRunningChars) - 1);
        matches++;
      }
    }

    if (matches == wordArrayLength && windowEnd - firstMatchIndex + 1 == totalAllowableWords) {
      //We have a first match 
      resultIndices.add(firstMatchIndex);

      System.out.println(str.substring(firstMatchIndex, totalAllowableWords+firstMatchIndex)); 

      String removeStringfromSeen = str.substring(firstMatchIndex, firstMatchIndex+wordLength);

      matches--; 
      wordFreqMap.put(removeStringfromSeen, wordFreqMap.get(removeStringfromSeen) + 1);

      firstMatchIndex = windowEnd - wordLength + 1;
    }

    windowStart++;
  }

}
return resultIndices;

}

public static void main(String[] args) {
List result = findWordConcatenation(“catfoxcatcatfoxcatfoxcat”, new String[] { “cat”, “fox” });
System.out.println(result);
result = WordConcatenation.findWordConcatenation(“catcat”, new String[] { “cat”, “fox” });
System.out.println(result);
}

#5

Here are some examples that your solution doesn’t handle correctly:

result = WordConcatenation.findWordConcatenation("catfoxcatcatfox", new String[] { "cat","cat","fox" });
System.out.println(result);
result = WordConcatenation.findWordConcatenation("catcatatcatatctcatca", new String[] { "cat","atc","tca" });
System.out.println(result);

The expected results are [0, 3, 6] and [8].

Additionally, it is not O(N), because your hash keys are complete words. Calculating the hash of a word is O(word.length()).

#6

I don’t get how it is similar with Maximum Sum Subarray of Size question?

#7

It’s similar to the brute force solution of Maximum Sum Subarray of Size K in a way that you go through every index of the given array and do the calculation on the subarray starting from that index.

I don’t think this problem follows the sliding window pattern either, it must be a mistake to say so in the solution.