Find if multiple nonsequential duplicates are present in the array

user_10604844 0
Viewed 82

[c,a,a,b,b,d], [c,a,b,b,d,d,a] or [a,a,b,b,c,d,d] should return false while [a,a,c,d,b,b] or [a,a,c,b,b,d] should return true as the duplicates are not consecutive.

public boolean findNSeqDup(String[] arr) {
    if(arr.length < 4){
        return false;
    }

    boolean isPrevDup = false;
    String prevString = "";
    for (int i = 0; i < arr.length; i++){
        if(arr[i].equals(prevString) && isPrevDup==true){
            System.out.println("true");
            return true;
        }
        else if(arr[i].equals(prevString) && isPrevDup==false){
            isPrevDup = true;
            prevString = "";
        }
        else if(!prevString.equals("") && !arr[i].equals(prevString)){
            prevString = "";
        }
        // for the first condition if the previous string is empty
        else {
            prevString = "";
        }
        prevString = arr[i];
    }
    System.out.println("false");
    return false;
}

The above code returns true to all conditions where it should return false ([c,a,a,b,b,d], [c,a,b,b,d,d,a] or [a,a,b,b,c,d,d]). What am I doing wrong? Will this be easier if I used a stack or a similar data structure?

arrays java
2 Answers

It seems using stack/deque to collect the counts of consecutive duplicates and singles could help resolve this task:

public static boolean findNonConsDup(String ... arr) {
    int n = arr.length;
    if(n < 4) {
        return false;
    }
    
    System.out.println(Arrays.toString(arr) + ": "); // debug print
    
    Deque<Integer> freqs = new ArrayDeque<>();
    String prev = arr[0];
    int cnt = 1;
    int prevFreq;
    
    for (int i = 1; i < n; i++) {
        if (!prev.equals(arr[i])) { // non-consecutive element found            
            if (freqs.isEmpty()) {
                freqs.push(cnt);
            }
            else {
                prevFreq = freqs.peek();
                // store the count of elements only when a single changes the duplicate or vice versa
                if (cnt == 1 && prevFreq > 1 || cnt > 1 && prevFreq == 1) {
                    freqs.push(cnt);
                    // early detection of non-consecutive duplicates
                    if (freqs.size() > 2) {
                        int p1 = freqs.pop();
                        int p2 = freqs.pop();
                        int p3 = freqs.pop();
                        // pattern found: at least 1 single separator between 2 duplicates
                        if (p1 > 1 && p2 == 1 && p3 > 1) {
                            return true;
                        } else { // restore queue
                            freqs.push(p3);
                            freqs.push(p2);
                            freqs.push(p1);
                        }
                    }
                }
            }
            cnt = 1;
        } else {
            cnt++;
        }
        prev = arr[i];
    }
    prevFreq = freqs.peek();
    if (cnt == 1 && prevFreq > 1 || cnt > 1 && prevFreq == 1) {
        freqs.push(cnt);
    }
    System.out.print(freqs + " -> "); // debug print
    return freqs.size() > 2 && freqs.pop() > 1 && freqs.pop() == 1 && freqs.pop() > 1;
}

Tests:

public static void main(String args[]) {
  System.out.println(findNonConsDup("c","a","b","d","a","d"));
  System.out.println(findNonConsDup("c","a","b","b","a","d"));
  System.out.println(findNonConsDup("c","a","b","b","b", "a","d", "d"));

  System.out.println(findNonConsDup("c","a","a","b","b","d"));
  System.out.println(findNonConsDup("c","a","b","b","d","d","a"));
  System.out.println(findNonConsDup("a","a","b","b","c","d","d"));
  System.out.println(findNonConsDup("c", "a","a","c","d","b","d","d"));
  System.out.println(findNonConsDup("a","a","c","d","b","d","d"));
  System.out.println(findNonConsDup("a","a","c","b","b","d","d"));
}

Output

[c, a, b, d, a, d]: [1] -> false
[c, a, b, b, a, d]: [1, 2, 1] -> false
[c, a, b, b, b, a, d, d]: [2, 1, 3, 1] -> true
[c, a, a, b, b, d]: [1, 2, 1] -> false
[c, a, b, b, d, d, a]: [1, 2, 1] -> false
[a, a, b, b, c, d, d]: [2, 1, 2] -> true
[c, a, a, c, d, b, d, d]: [2, 1, 2, 1] -> true
[a, a, c, d, b, d, d]: [2, 1, 2] -> true
[a, a, c, b, b, d, d]: true
user_132798310

Hi there are multiple problems with your code.

First: all of your prevString = ""; assignments are rendered useless, because they are overwritten in the last line in the for block: prevString = arr[i]; You should try to use another boolean variable to store whether the last char was a duplicate, too.

Here's a much simpler approach why don't you just start with the 4th element and compare the nth with the n-1th and the n-2th with the n-3th element:

  public boolean findNonConsDup(String[] arr) {
    if(arr.length < 4){
      return false;
    }

    for (int i = 3; i < arr.length; i++) {
      if (arr[i].equals(arr[i-1]) && arr[i-2].equals(arr[i-3])) {
        return true;
      }
    }
    return false;
  }
user_29872730
Related