# Accepted but quite slow solution, BFS, try all possible insertions

• Basically try every possible insertion position and character. If found a solution, returns.

``````    public int findMinStep(String board, String hand) {
int [] count = new int[5];
for (int i=0;i<board.length();i++){
if (board.charAt(i)=='R') count[0]++;
if (board.charAt(i)=='Y') count[1]++;
if (board.charAt(i)=='B') count[2]++;
if (board.charAt(i)=='G') count[3]++;
if (board.charAt(i)=='W') count[4]++;
}
for (int i=0;i<hand.length();i++){
if (hand.charAt(i)=='R'&&count[0]>0) count[0]++;
if (hand.charAt(i)=='Y'&&count[1]>0) count[1]++;
if (hand.charAt(i)=='B'&&count[2]>0) count[2]++;
if (hand.charAt(i)=='G'&&count[3]>0) count[3]++;
if (hand.charAt(i)=='W'&&count[4]>0) count[4]++;
}
for (int i=0;i<5;i++){
if (count[i]<3 && count[i]>0) return -1;
}

HashMap<Character, Integer> handMap = new HashMap<Character, Integer>();
for (int i=0;i<hand.length();i++){
if (!handMap.containsKey(hand.charAt(i)))
handMap.put(hand.charAt(i), 0);
handMap.put(hand.charAt(i), handMap.get(hand.charAt(i))+1);
}

ArrayDeque<String> bq = new ArrayDeque<String>();
ArrayDeque<HashMap<Character, Integer>> hq = new ArrayDeque<HashMap<Character, Integer>>();
int step = 0;
while(!bq.isEmpty()){
step++;
int l = bq.size();
for (int i=0;i<l;i++){
String b = bq.poll();
HashMap<Character, Integer> h = hq.poll();
for (int j=1;j<=b.length();j++){

for (char k:h.keySet()){
String t = "";
if (j==b.length()&& j>1) continue;
if ((j==b.length() && j==1)|| k==b.charAt(j)||k==b.charAt(j-1))
t = ins(b, k, j);
else continue;
if (t=="") return step;
HashMap<Character, Integer> nmap = (HashMap<Character, Integer>) h.clone();
if (nmap.get(k)>1) nmap.put(k, nmap.get(k)-1);
else
nmap.remove(k);
}
}
}
}
return -1;
}

String ins (String b, char c, int p){
int l = p-1, r = p, cur = 1, np=p, l1=0,r1=0;
StringBuilder res = new StringBuilder(b);
while (l>-1 || r<b.length()){
while (l>-1 && b.charAt(l)==c){
l--;
cur++;
}
while (r<b.length() && b.charAt(r)==c){
r++;
cur++;
}

if (cur<3){
res.delete(l1,r1);
res.insert(np, c);
return res.toString();
}
else{
if (l==-1 && r==b.length())
return "";
if (l>-1){
c = b.charAt(l);
l1 = l;
r1 = Math.min(r,b.length());
np = l;
cur = 1;
l--;

}
else{
c= b.charAt(r);
l1 = Math.max(l, 0);
r1 = r+1;
r++;
np = l+1;
cur = 1;
}
}
}
return Character.toString(c);
}
``````

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