# Simple Java Solution with Two Pointers and Map

• My idea is pretty simple. Just build a map for the words and their relative count in L. Then we traverse through S to check whether there is a match.

``````public static List<Integer> findSubstring(String S, String[] L) {
List<Integer> res = new ArrayList<Integer>();
if (S == null || L == null || L.length == 0) return res;
int len = L[0].length(); // length of each word

Map<String, Integer> map = new HashMap<String, Integer>(); // map for L
for (String w : L) map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);

for (int i = 0; i <= S.length() - len * L.length; i++) {
Map<String, Integer> copy = new HashMap<String, Integer>(map);
for (int j = 0; j < L.length; j++) { // checkc if match
String str = S.substring(i + j*len, i + j*len + len); // next word
if (copy.containsKey(str)) { // is in remaining words
int count = copy.get(str);
if (count == 1) copy.remove(str);
else copy.put(str, count - 1);
if (copy.isEmpty()) { // matches
break;
}
} else break; // not in L
}
}
return res;
}
``````

At first I was gonna to use a set for words. Owing to the fact that duplicate is allowed in L, we need to use map instead.

• ``````public static  List<Integer>	 findSubString(String s ,String [] L) {
List<Integer> list = new ArrayList<Integer>();
if(s==null|| s==""||L==null||L[0].length()==0)
return list;
Map<String, Integer> map = new   HashMap<String ,Integer>();
int len=L[0].length();
for (String  tmp : L) {
if(!map.containsKey(tmp)) {
map.put(tmp, 1);
}
}
for (int i = 0; i <s.length()-L.length*len; i++) {
Map<String , Integer> copy = new HashMap<>(map);
for(int j=0;j<L.length;j++) {
String tmp_stringString = s.substring(i+j*len, i+j*len+len);
if (copy.containsKey(tmp_stringString)) {
copy.remove(tmp_stringString);
}else {
continue;
}
}
if (copy.isEmpty()) {
}
}
return list;
}
``````

the same way use List can save about 50% time

• I dont think this is two pointer ways, it is simply iteration the string

• There are i and j, which are the two pointers. Two pointers can go from either direction. This is the sliding window version.

• you code can't pass now, maybe there are some new test cases. Time limit exceeded.

• yes. I got “Time limit exceeded” too by the same algorithm T^T

• Yes, I also got TLE. I applied the same algorithm to Minimum Subarray Sum and got TLE. What is the problem with this method?

• @jocelynayoga I think the copy.remove() is time-consuming, and it's called whenever a substring matches the strings of words. The method should be replaced be checking if the string's count is less than 1. my code with a similar logic got AC with this improvement.

• @hizhaojun Hi, hizhaojun, could you please share your AC code? I have tried to replace copy.remove() by checking if the string's count is less than 1, but still got TLE. Thank you.

• @SherryH hope it help.

``````public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int n = words.length, m = words[0].length();
List<Integer> res = new ArrayList();
/*Store string array with hashtable.*/
HashMap<String, Integer> map = new HashMap();
for (String str : words) {
if (map.containsKey(str)) map.put(str, map.get(str)+1);
else map.put(str, 1);
}
/*m is the length of each word in array words, each time get a substring of length m to check if it exits in words*/
for (int i = 0; i <= s.length()-n*m; i++) {
HashMap<String, Integer> copy = new HashMap(map);
/*if it exits, use another hashset to avoid duplicate and count the number to reach n, the number of words in array words*/
int k = n, j = i;
while (k > 0) {
String str = s.substring(j, j+m);
if (!copy.containsKey(str) || copy.get(str) < 1) break;
copy.put(str, copy.get(str)-1);
k--; j+=m;
}
}
return res;
}
}
``````

• @hizhaojun Hi, thank you so much for your answer. It's strange that now my code also got accepted even though I didn't change anything. :)

• Can anyone clarify the time complexity? I think it is O(N ^ 2),
and N = len(S) / (each word len).

• @zfuuuuu I think so. It's very intuitive. But it seems like it cannot pass the large test case?

• I got TLE error with this solution, how can I fix it?

• cause judge HashMap copy isEmpty() runs too many times,i try to remove it to the outside of loop,then it works.
code revise as list:
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res=new ArrayList<Integer>();
int len=words[0].length();
if(s.length()==0||words.length==0) return res;
Map<String,Integer> map= new HashMap<>();
for(String str:words)
map.put(str,(map.containsKey(str)?map.get(str)+1:1));
for(int i=0;i<=s.length()-lenwords.length;i++){
Map<String,Integer> cpy=new HashMap<>(map);
for(int j=0;j<words.length;j++){
String str=s.substring(i+len
j,i+len*j+len);
if(cpy.containsKey(str)){
int index=cpy.get(str);
if(index==1) cpy.remove(str);
else cpy.put(str,index-1);
}
else break;
}
if(cpy.isEmpty()){
}
}
return res;
}
}

• For those who get Time Limit Exceeded, see my optimized version. link text

• int n = words.length, m = words[0].length();
List<Integer> res = new ArrayList();
/Store string array with hashtable./
HashMap<String, Integer> map = new HashMap();
for (String str : words) {
if (map.containsKey(str)) map.put(str, map.get(str)+1);
else map.put(str, 1);
}
/m is the length of each word in array words, each time get a substring of length m to check if it exits in words/
for (int i = 0; i <= s.length()-n*m; i++) {
HashMap<String, Integer> copy = new HashMap(map);
/if it exits, use another hashset to avoid duplicate and count the number to reach n, the number of words in array words/
int k = n, j = i;
while (k > 0) {
String str = s.substring(j, j+m);
if (!copy.containsKey(str) || copy.get(str) < 1) break;
copy.put(str, copy.get(str)-1);
k--; j+=m;
}
}
return res;

I am still getting Time Limit exceed error error with this code for following input
"abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab"
["ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba"]

• Easy to understand. good solution.

• I got a TLE for the similiar solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.