Maximum String Mismatches in Java

I recently encountered the same question in one of the competency tests, I don't know about above solution, but my implementation below in python works for above problem

import itertools
def maximum_mismatches(s,n):
    if len(set(s)) == 1:
        return 0
    maxc = 0
    for str_c in set(itertools.permutations(s,n)):
        rev_str = str_c[::-1]
        counter = 0
        for i in range(n):
            if str_c[i] != rev_str[i]:
                counter += 1
        if maxc < counter:
            maxc = counter
    return maxc

I have tested for multiple test cases, it is working

Calculate the frequency of each character in the string and then take the difference of frequency of each character. See the code example in Java. It returns the max mismatch of characters of a string & it's reverse, given that a substring in the original string can be reversed any number of times.

Examples: 1. cantaaaa (answer = 6), 2. cbbaa (answer = 4), 3. aaaaabbbbccdd (answer = 12)

public static int maxMismatch(String str){
    if(str == null || str.length() <= 1) return 0;

    int freq[] = new int[26];

    for(int i = 0; i < str.length(); i++){
        freq[str.charAt(i) - 97]++;
    }

    int diff = 0;
    for(int i = 0; i < freq.length; i++){
        diff = Math.abs(freq[i] - diff);
    }

    return str.length() - diff;
}

import itertools as it
def mismatch(S,n):
    max =0
    for x in set(it.permutations(S[::-1],n)):
        cnt = 0
        for i in range(n):
            if x[i]!=S[i]:
                cnt+=1
        if cnt > max:
            max=cnt
    return max

#include <bits/stdc++.h>
using namespace std;
int max_mismatch(string s)
{
  unordered_map<char,int> fmap;
  for(auto &ch:s)
    fmap[ch]++;
  vector<int> tempV;
  for(auto &[_,f]:fmap)
     tempV.push_back(f);
  sort(tempV.begin(),tempV.end(),greater<int>());    
  vector<int> freq(tempV.size());
  int diff=0,left=0,right=freq.size()-1;
  bool leftinsert=true;
  for(auto f:tempV)
  {
      if(leftinsert)
          freq[left++]=f;
      else
         freq[right--]=f;
      leftinsert^=1;     
  }
  /*for(auto &val:freq)
     cout<<val<<" ";
  cout<<endl;  */
  left=0;right=freq.size()-1;
  for(int i=0;i<s.size()/2;i++)
  {
     if(left==right)
       break;
     if(!(--freq[left])) left++;
     if(!(--freq[right])) right--;
     diff+=2;
  }
  return diff;        
}
int main()
{
    string s="aatacanaa";
    cout<<max_mismatch(s);
}

First a function to calculate the mismatch score, using this spec:

Mismatch(S) is defined as number of corresponding positions were characters are different in S and reverse(S). For example : S = abab, reverse(S) = baba. Number of mismatches = 4. S= abca. Number of mismatches = 2.

We don't need to actually reverse the string. Just compare the first character with the last, then the second with the second last, etc. I find it straightforward to use two index variables for something like this:

int mismatches(String s) {
    int result = 0;
    int i = 0;
    int j = s.length() - 1;
    while (j >= 0) {
        if (s.charAt(i) != s.charAt(j)) result++;
        i++;
        j--;
    }
    return result;
}

And here are some tests to increase our confidence:

@Test
public void test_mismatches() {
    assertEquals(0, mismatches(""));
    assertEquals(0, mismatches("a"));
    assertEquals(0, mismatches("aa"));
    assertEquals(2, mismatches("ab"));
    assertEquals(0, mismatches("aaa"));
    assertEquals(2, mismatches("aab"));
    assertEquals(2, mismatches("abc"));
    assertEquals(0, mismatches("aaaa"));
    assertEquals(2, mismatches("aaab"));
    assertEquals(2, mismatches("aaba"));
    assertEquals(4, mismatches("abcd"));
}

Now let's find the max mismatch. Here is the spec:

You are given a string S of length N. You can select and reverse any substring of S of any length. You are allowed to perform this operation many number of times.

Determine maximum number of mismatches by performing operation.

This is unclear and has typos. It is lazily written and if it was client work, I would be asking for a clarification. I've been burned in the past by working from unclear specs, and building something that the client didn't intend.

I think the use of the word "reverse" is a misnomer. I think it is to help hint at a solution for calculating the mismatch. The spec should be:

You are given a string. Determine maximum number of mismatches from any substring. For clarity, the original string is a valid substring of itself.

With this revised spec, we can just use a nested for loop to traverse the search space:

int maxMismatches(String s) {
    int result = 0;
    for (int i = 0; i < s.length(); i++)
        for (int j = s.length(); j > i; j--) {
            int mismatch = mismatches(s.substring(i, j));
            if (mismatch > result)
                result = mismatch;
        }
    return result;
}

And some tests:

@Test
public void test_max_mismatches() {
    assertEquals(0, maxMismatches(""));
    assertEquals(0, maxMismatches("a"));
    assertEquals(0, maxMismatches("aa"));
    assertEquals(2, maxMismatches("ab"));
    assertEquals(2, maxMismatches("aba"));
    assertEquals(4, maxMismatches("aabbaa"));
    assertEquals(6, maxMismatches("aaabcda"));
}

There is a gap in this set of tests. Some of the test strings require truncating the start to find the max. Some require truncating the end, but none require truncating both the start and end.

Both functions have obvious optimisations but they reduce clarity in a scenario where I don't think performance is important.

Here you could first reverse the giving string and then just iterate through the giving string and compare character at each index in both the giving string and reversed string and if there is a mismatch increase the counter.

Check the below code

public static void main(String args[])throws IOException {

    String s = "abab";
    System.out.println(solve(s,s.length()));
}

static int solve( String s, int n)
{   
    //this can also be used to reverse string
    //String reversed = new StringBuilder(s).reverse().toString();

    String revStr = Stream.of(s)
            .map(word->new StringBuilder(word).reverse())
            .collect(Collectors.joining(" "));

    int counter = 0;
    for(int loop=0; loop < n; loop++){
        if(s.charAt(loop)!=revStr.charAt(loop)){
            ++counter;  
        }
    }
    return counter;
}