Standard test program is wrong?

  • 48

    Hi all,

    I tried case "RRWWRRBBRR", "WB". The test program gave the expected answer -1. However, I thought the answer might be 2. Because:


    The possible reason might be the first [W] was inserted but not adjacent to a W in the sequence. I read the description twice but didn't find any condition about it.

    Could someone give me some ideas about it?

  • 0

    agree with you~
    due to this kind of condition, the sequence of inserting is influential to the result and it's meaningful to insert one color between two same color balls. So it takes more time to right a really "correct" program than the standard test program.

  • 1

    Hi @herbix,

    Thanks for submitting such good test cases, to be honest, the original solution hasn't considered this situation.

    Truly sorry for that, we'll fix this problem as soon as possible.

    If it has been solved, we'll let you know in the first time.

    Leetcode Team.

  • 1

    Your test case is really good! I have seen many submitted answers and all of them choose their searching path intutively without necessary logic proof. My program using DFS to search all the solution space with strict pruning cannot satisfy the time limit. However, many submitted answers choose to detect only a small part of solution space but they can pass the online test! I don't believe they are right although I cannot figure out why they can ignore other possible solutions. Your case offers me a good example to beat them.
    Could you offer me your program which can pass both this test case and online test? Thx.

  • 0

    @love_FDU_llp I am wondering whether those submitted answers need to be tested again since many of them cannot provide correct result in this case. It feels bad to get a wrong answer when you want to get help from others.

  • 0

    @zx731 Sorry about that I didn't write a program that can pass the both cases. It is passed with the "unproved" algorithm.
    I tried DFS with pruning but time limit exceeded. Maybe time limit shouldn't be so strict if this test case is considered.

  • 0

    @herbix said in Standard test program is wrong?:


    My code yields output 2, too...
    It seems the test program has problem and some more test cases need to be added as well.


  • 0

    @1337c0d3r Should we consider putting this question on hold?

  • 0

    Nice test case! For this question, can we either relax restriction on time complexity or add one more restriction on the description: "Ball only can be inserted beside a ball with same color"?

  • 0

    Same here. I used dfs and memoization. Code follows:

    public class Solution {
        private Map<String, Map<String, Integer>> mem = new HashMap<>();
        public int findMinStep(String board, String hand) {
            if(mem.containsKey(board) && mem.get(board).containsKey(hand)) {
                return mem.get(board).get(hand);
            int bL = board.length(), hL = hand.length();
            if(bL == 0) {return 0;}
            if(hL == 0) {return -1;}
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < hL; j++) {
                char c = hand.charAt(j);
                //not use
                String remain = hand.substring(0, j) + hand.substring(j + 1);
                int next = findMinStep(board, remain);//not use ball, count as no extra step
                if(next != -1) {
                    min = Math.min(next, min); 
                for(int i = 0; i <= bL; i++) {
                    if(i != 0 && i < bL && board.charAt(i) == board.charAt(i - 1)) {continue;}
                    String newBoard = board.substring(0, i) + c + (i == bL ? "" : board.substring(i));
                    next = findMinStep(collapse(newBoard), remain);
                    if(next != -1) {
                        min = Math.min(next + 1, min);
                     //use one ball, count as one step
            int res = min == Integer.MAX_VALUE ? -1 : min;
            return ret(board, hand, res);
        int ret(String board, String hand, int res) {
            Map<String, Integer> m = mem.getOrDefault(board, new HashMap<>());
            m.put(hand, res);
            mem.put(board, m);
            return res;
        String collapse(String s) {
            for(int i = 0, j = 0; j < s.length(); j++) {
                if(s.charAt(j) == s.charAt(i)) {continue;}
                if(j - i >= 3) {
                    return collapse(s.substring(0, i) + s.substring(j));
                else {
                    i = j;
            return s;

Log in to reply

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