Maximum String Mismatches in Java

Question

I was recently going through a question in codehub and I was unable to solve this query. Can anyone help me how can this be solved?

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.

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.

Pseudo code :

static int solve( String S, int n)
{
//To do
}

Will be helpful if some one can explain once the code is done how this can be interpreted more easily and approached to solve.

Answer 1

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