educative.io

O(N+M) time solution in Java (readable)

Courses
,
#1 
    class WordConcatenation {
  public static List<Integer> findWordConcatenation(String str, String[] words) {
    List<Integer> resultIndices = new ArrayList<Integer>();
    Map<String, Integer> wordsToMatch = new HashMap<>();
    int wordLength;
    int windowStart = 0;
    int sequenceStart = 0;
    int matchedWords = 0;  
    boolean invalidSequence = false;  

    Arrays.stream(words).forEach(word -> wordsToMatch.put(word, 1));
    wordLength = words[0].length();

    for(int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      if (windowEnd - windowStart + 1 == wordLength) {
          String currWord = str.substring(windowStart, windowStart + wordLength);
          wordsToMatch.compute(currWord, (key, val) -> val - 1);
          if (wordsToMatch.get(currWord) == 0) {
            matchedWords += 1;            
            if (matchedWords == words.length) {
              resultIndices.add(sequenceStart);
            }
          } else {
            invalidSequence = true;
          }          

          if (invalidSequence || matchedWords == words.length) {
            String leftWord = str.substring(sequenceStart, sequenceStart + wordLength);
            wordsToMatch.compute(leftWord, (key, value) -> value + 1);
            if (wordsToMatch.get(leftWord) > 0) {
              matchedWords -= 1;
            }
            sequenceStart = sequenceStart + wordLength;
            windowStart += wordLength;
            invalidSequence = false;
          } else {
            windowStart += wordLength;
          }
      }
    }

    return resultIndices;
  }
}