Find Substring Concatenation Indices
This program finds indices where concatenation of words occurs.
Problem Statement
Write a Java program to find indices of "barfoo" in "barfoothefoobarman" using words ["foo","bar"].
Source Code
| 1 | import java.util.*; |
| 2 | public class SubstringConcatenationIndices { |
| 3 | public static void main(String[] args) { |
| 4 | System.out.println("Eduinq Substring Concatenation Indices"); |
| 5 | String s="barfoothefoobarman"; |
| 6 | String[] words={"foo","bar"}; |
| 7 | int wordLen=words[0].length(), totalLen=wordLen*words.length; |
| 8 | List<Integer> indices=new ArrayList<>(); |
| 9 | for(int i=0;i<=s.length()-totalLen;i++){ |
| 10 | String sub=s.substring(i,i+totalLen); |
| 11 | List<String> list=new ArrayList<>(Arrays.asList(words)); |
| 12 | for(int j=0;j<sub.length();j+=wordLen){ |
| 13 | String w=sub.substring(j,j+wordLen); |
| 14 | if(list.contains(w)) list.remove(w); |
| 15 | else break; |
| 16 | } |
| 17 | if(list.isEmpty()) indices.add(i); |
| 18 | } |
| 19 | System.out.println("Indices: "+indices); |
| 20 | } |
| 21 | } |
Program Output
Eduinq Substring Concatenation Indices Indices: [0, 9]
Explanation
A sliding window extracts a substring of total word-length size at every position, and each word-sized chunk is checked against a mutable copy of the words list, removing matches, so an empty list at the end confirms a valid concatenation index.