educative.io

Educative

Need help with my almost solution

import java.util.*;

public class WordConcatenation {

public static List<Integer> findWordConcatenation(String str, String[] words) {
     // TODO: Write your code here
    int windowStart = 0, matched = 0, index = 0;
    StringBuffer rsb = new StringBuffer();
    StringBuffer lsb = new StringBuffer();
    List<Integer> indices = new ArrayList<Integer>();
    HashMap<String, Integer> map = new HashMap<>();
    for(String word : words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }
    

    for(int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      
      char right = str.charAt(windowEnd);
      rsb.append(right);
      if(map.containsKey(rsb.toString())) {
        map.put(rsb.toString(), map.get(rsb.toString()) - 1);
        if(map.get(rsb.toString()) == 0) {
          matched++;
          System.out.println("String Buffer : " + rsb.toString());
          System.out.println("Matched: " + matched);
          rsb.delete(0, rsb.length());
          
          
        }
        
      }
      

      if(matched == map.size()){
        index = windowStart;
        indices.add(index);
      } 

      while(matched == map.size()) {
        char left = str.charAt(windowStart);
        lsb.append(left);
       
        if(map.containsKey(lsb.toString())) {
          if(map.get(lsb.toString()) == 0){
            matched--;
            System.out.println("String Buffer : " + rsb.toString());
	        System.out.println("Matched: " + matched);
            
          }
          map.put(lsb.toString(), map.get(lsb.toString()) + 1);
          lsb.delete(0, lsb.length());
        }
        windowStart++;
      }
    }
    
    return indices;
 }

public static void main(String[] args) {
	List<Integer> result = WordConcatenation.findWordConcatenation("catfoxcat", new String[] { "cat", "fox" });
	System.out.println(result);
	result = WordConcatenation.findWordConcatenation("catcatfoxfox", new String[] { "cat", "fox" });
	System.out.println(result);
}

}

I feel like Im missing a super simple step to make this solution work. Can someone please help me

Hi @Dylan_Burns ,
Your solution works only for the inputs where word concatenation starts from the zeroth index of the given string. Otherwise, it doesn’t keep track of the concatenations. For example, the inputs given below would not give the required output.

List<Integer> result = WordConcatenation.findWordConcatenation("catcatfoxfox", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("foxfoxfoxcat", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("afoxcat", new String[] { "cat", "fox" });
    System.out.println(result);

To resolve this, we can use a nested loop to go through all the combinations. We need to keep track of all the concatenations, not just the ones which start from zero index only.

Also, there is a more simple way to solve this problem by using Map. See the code below:

class WordConcatenation {
  public static List<Integer> findWordConcatenation(String str, String[] words) {
    // TODO: Write your code here
    Map<String, Integer> wordFrequencyMap = new HashMap<>();
    for (String word : words)
      wordFrequencyMap.put(word, wordFrequencyMap.getOrDefault(word, 0) + 1);

    List<Integer> resultIndices = new ArrayList<Integer>();
    int wordsCount = words.length, wordLength = words[0].length();

    for (int windowStart = 0; windowStart <= str.length() - wordsCount * wordLength; windowStart++) {
      Map<String, Integer> wordsSeen = new HashMap<>();
      for (int windowEnd = 0; windowEnd < wordsCount; windowEnd++) {
        int nextWordIndex = windowStart + windowEnd * wordLength;
        String word = str.substring(nextWordIndex, nextWordIndex + wordLength);
        if (!wordFrequencyMap.containsKey(word))
          break;

        wordsSeen.put(word, wordsSeen.getOrDefault(word, 0) + 1); 

        if (wordsSeen.get(word) > wordFrequencyMap.getOrDefault(word, 0))
          break;

        if (windowEnd + 1 == wordsCount)
          resultIndices.add(windowStart);
      }
    }

    return resultIndices;
  }
  public static void main(String[] args) {
    List<Integer> result = WordConcatenation.findWordConcatenation("catfoxcat", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("catcatfoxfox", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("catfoxfox", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("foxfoxfoxcat", new String[] { "cat", "fox" });
    System.out.println(result);
    result = WordConcatenation.findWordConcatenation("afoxcat", new String[] { "cat", "fox" });
    System.out.println(result);
  }
}

The above code now fulfills all the test cases.

I hope this is helpful :slight_smile:
Happy Learning!