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

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?

https://stackoverflow.com/questions/65711151/count-number-of-matching-strings-after-replacing-a-character-and-all-its-occurre January 14, 2021 at 07:13AM