Count number of matching strings after replacing a character and all its occurrence

Question

I have an array of strings arr and another input string s.

Now my task is to pick a character from s and replace all the occurrences of that letter in s with another character. Then rearrange the characters if needed but this is optional. Now count how many of them are matching with array elements.

I have written code in Java for this, but the approach I followed is not correct.

Example: s = aabbcdbb

arr = {"aabbcdbbb", "aabbcdb", "aabbxdbb", "aabbbdbb", "aacccdcc", "ddbbcdbb", "eebbcdbb"}

Output :

5

explanation:

length of s = 8
sorting s = aabbbbcd

arr[0] = has 9 characters i.e more than s length so ignored
arr[1] = has 7 characters i.e less than s length so ignored
arr[2] = sorting : aabbbbdx. replace x with c and rearranging it makes this as aabbbbcd
arr[3] = sorting : aabbbbbd. replace 1 occurrence of b with c and rearranging it makes this as aabbbbcd
arr[4] = sorting : aacccccd. replace 4 occurrences of c with b and rearranging it makes this as aabbbbcd
arr[5] = sorting : bbbbcddd. replace 2 occurrences of d with a and rearranging it makes this as aabbbbcd
arr[6] = sorting : bbbbcdee. replace e with a and rearranging it makes this as aabbbbcd

so arr[2], arr[3], arr[4], arr[5], arr[6] matches the given requirement so output is 5.

I tried this program but this fails for some inputs:

static int process(String s, String[] arr) {
    int matches = 0;
    Map<Character, Integer> m = new HashMap<>();
    
    // sort s
    char[] c = s.toCharArray();
    Arrays.sort(c);
    s = new String(c);
    c = s.toCharArray();
    
    // get each char of s and count its occurrences
    for(char k : c) {
        m.put(k, m.getOrDefault(k, 0)+1);
    }
    
    for(String s1 : arr) {
        // get array element
        char[] c1 = s1.toCharArray();
        // check if array element length matches with input string length
        if(c1.length == c.length) {
            // count each occurrence of char into array of alphabets
            int[] chars = new int[26];
            for(char k1: c1) {
                chars[k1-'a']++;
            }
            
            // decrement count by checking with map
            for(char k : m.keySet()) {
                chars[k-'a'] -= m.get(k);
            }
            
            boolean f1 = false;
            boolean valid = true;
            int mismatch = 0;
            int notzeros = 0;
            // get each element from array of chars
            for(int i=0; i<26; i++) {
                int ch = chars[i];
                // value not zero
                if(ch != 0) {
                    // count number of non zeros
                    notzeros++;
                    // f1 is true, means its second occurrence of non zero element
                    if(f1) {
                        if(ch > 0) {
                            // check if values do not match
                            if(mismatch*-1 != ch) {
                                valid = false;
                                break;
                            }
                        } else {
                            // check if values do not match
                            if(mismatch != ch*-1) {
                                valid = false;
                                break;
                            }
                        }
                    }
                    // get the mismatch count and set the value of flag to true
                    f1 = true;
                    mismatch = ch;
                }
                // if non zero elements more than 2 then we can ignore this array element
                if(notzeros > 2) {
                    valid = false;
                    break;
                }
            }
            //  check for possible solution.
            if(valid && f1) {
                matches++;
            }
        }
    }
    return matches;
}

This program works for the given test case.

Now if I send the below input it fails.

example: s = abba
arr = {'aadd" ,"abbb"};

expected output: 1

explanation:
sorted s = aabb
arr[0] = aadd, replace d with b then we get aabb
arr[1] = abbb, we cannot replace all occurrences of a single character to get s as output, so ignored.

So the output is 1.

But my program is printing 2 which is not correct.

My approach to solve this task is not correct, what is the correct way to do this?

Answer 1

First of all, it seems the explanation you provided is based on a slightly misunderstood formulation of the problem. The problem consists of checking whether all occurrences of a character can be replaced with a different character in the string s, not the string in the array.

So for example, with s = "aabbcdbb", and array string "aabbbdbb", you can replace the c character in s with a b to obtain the array string. It's not the other way around. That explains the inconsistency of the expected outputs for the two input samples (as raised in the comments).

Your implementation is generally correct but fails on a special case. The way you're solving it is by basically generating a "diff" array containing the difference in occurrence for each character. You then expect that in the diff, you have only two different occurrences that negate each other. To illustrate with the previous example, you map the characters of s:

a -> 2
b -> 4
c -> 1
d -> 1

similarly with the current array element:

a -> 2
b -> 5
d -> 1

the difference will be:

b -> 1
c -> -1

This fails when you have s = "aabb" and a string "abbb", where the diff is:

a -> -1
b -> 1

The problem here is that both characters a and b occur in the string "abbb". This should fail the match check. The reason is: if we want to go from "abbb" to "aabb", we would need to replace a b with an a. But "abbb" already has an a character, which would not have been there if the opposite side replaced a with b.

The code can be modified to handle this case (the part that uses diffInS1):

for(String s1 : arr) {
    // get array element
    char[] c1 = s1.toCharArray();
    // check if array element length matches with input string length
    if(c1.length == c.length) {
        // count each occurrence of char into array of alphabets
        int[] chars = new int[26];
        int[] diff = new int[26];
        for(char k1: c1) {
            chars[k1-'a']++;
            diff[k1-'a']++;
        }
        
        // decrement count by checking with map
        for(char k : m.keySet()) {
            diff[k-'a'] = chars[k-'a'] - m.get(k);
        }
        
        boolean valid = true;
        int mismatch = 0;
        int notzeros = 0;
        int diffInS1 = 0;
        // get each element from array of chars
        for(int i=0; i<26; i++) {
            int ch = diff[i];
            // value not zero
            if(ch != 0) {
                // count number of non zeros
                notzeros++;
                // second occurrence of non zero element
                if(notzeros > 1) {
                    // check if values do not match
                    if(mismatch*-1 != ch) {
                        valid = false;
                        break;
                    }
                }
                if(chars[i] > 0) {
                    diffInS1++;
                }
                // get the mismatch count
                mismatch = ch;
            }
            // if non zero elements more than 2 then we can ignore this array element
            if(notzeros > 2 || diffInS1 == 2) {
                valid = false;
                break;
            }
        }
        //  check for possible solution.
        if(valid && notzeros > 0) {
            matches++;
        }
    }
}