Максимальное несовпадение строк в Java

Question

Недавно я просматривал вопрос в codehub и не смог решить этот запрос. Кто-нибудь может мне помочь, как это можно решить?

Вам дана строка S длиной N. Вы можете выбрать и повернуть любую подстроку S любой длины. Вам разрешено выполнять эту операцию много раз.

Определение максимального количества несовпадений путем выполнения операции.

Несоответствие (S) определяется как количество соответствующих позиций, в которых символы различаются в S и наоборот (S). Например: S = abab, реверс (S) = баба. Количество несоответствий = 4. S = abca. Количество несоответствий = 2.

Псевдокод:

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

Будет полезно, если кто-нибудь сможет объяснить, как только код будет сделан, как его можно легче интерпретировать и приблизить к решению.

Answer 1

Вы можете попробовать это ниже:

static int solve( String S, int n)
{
        int mismatch_count = 0; 
        StringBuilder reverse_input = new StringBuilder(); 
        reverse_input.append(S); 
        reverse_input = reverse_input.reverse(); 
        char[] rev = reverse_input.toString().toCharArray();
        char[] ch = S.toCharArray();
        for (int i = 0; i < n; i++) {
            if(ch[i]!=rev[i]){
                mismatch_count += 1;
            }
        }
        System.out.println(mismatch_count); 
}

Answer 2

Я недавно сталкивался с тем же вопросом в одном из тестов на компетентность, я не знаю о вышеупомянутом решении, но моя реализация ниже в python работает для вышеуказанной проблемы

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

Я тестировал для несколько тестовых случаев, это работает

Answer 3

Здесь вы можете сначала перевернуть строку выдачи, а затем просто выполнить итерацию по строке выдачи и сравнить символы в каждом индексе как в строке выдачи, так и в обратной строке, а в случае несоответствия увеличить счетчик.

Проверка код ниже

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;
}