Java程序，最小化字符改变以使字符串的左右旋转相同

在这个问题中，我们需要改变给定字符串中的最小字符，使其左右旋转相同。在字符串中，我们可以观察到，如果字符串的长度为奇数且所有字符相同，或者字符串的长度为偶数且偶数和奇数索引处的字符相同，则只能使字符串的左右旋转相同。

例如，

• abab – 字符串的左右旋转是baba和baba。

• aaa – 字符串的左右旋转是aaa和aaa。

• abc – 字符串的左右旋转分别是bca和cab。

• aabb – 字符串的左右旋转是abba和baab。

问题描述 - 我们给出了一个包含字母字符的字符串str。字符串的大小等于N。我们需要改变最小数量的字符，使字符串的左右旋转相同。

示例案例

输入

str = "tuto"

输出

1

解释 - 我们要么需要将’u’ -> ‘o’或’o’ -> ‘u’来使字符串的左旋和右旋相同。

输入

str = "abcde";

输出

4

说明 – 为了使左旋和右旋相同，我们需要将所有字符都与字符串长度相同。

输入

str = ‘mnmnmnmnmnmn’

输出

0

解释 –字符串的左右旋转已经相同。

方法1

在这种方法中，我们将根据上面讨论的观察结果实现逻辑。如果字符串长度是奇数，我们将计算使所有字符相等的最小成本，如果字符串长度是偶数，我们将计算使字符串的偶数和奇数索引处的所有字符相等的最小成本。

算法

步骤1 –将字符串的长度存储在“len”变量中。同时，将“min_chars”初始化为字符串长度，因为我们假设最初字符串的所有字符都不同。

步骤2 –如果字符串长度是偶数，按照以下步骤进行操作。

步骤2.1 –定义长度为128的“evenPosFreq”和“oddPosFreq”数组，用于存储给定字符串中每个字符的频率。

步骤2.2 –开始遍历字符串，如果“p”是偶数，则在“evenPosFreq”数组中以字符的ASCII值为索引的位置上的值加1。否则，在“oddPosFreq”数组中的相应位置上的值加1。

步骤2.3 –现在，我们需要找到偶数和奇数位置上任意字符的最大频率。

步骤2.4 –定义“MaxFreqEven”和“MaxFreqOdd”变量，并初始化为零。同时，开始遍历频率数组，从两个数组中获取最大值，并将其存储在“MaxFreqEven”和“MaxFreqOdd”变量中。

步骤2.5 –在min_chars变量中，存储从字符串长度中减去“MaxFreqEven”和“MaxFreqOdd”值后的结果。

步骤3 –如果字符串长度是奇数，按照以下步骤进行操作。

步骤3.1 –定义“allCharFreq”数组以存储每个字符的频率。同时，通过遍历字符串将每个字符的频率存储在其中。

步骤3.2 –定义maxChar变量以存储具有最大频率的字符。遍历数组并找到数组中的最大元素。

步骤3.3 –在min_chars变量中，存储从字符串长度中减去maxChars值后的结果。

步骤4 –返回min_chars变量的值。

例子

public class TP {
    public static int findMinCharRemoval(String alpha) {
        int len = alpha.length();
        // Initially, let's say we need to remove all characters
        int min_chars = len;
        // For the odd length of the string
        if (len % 2 == 0) {
            // Defining array to store the frequency
            int[] evenPosFreq = new int[128];
            int[] oddPosFreq = new int[128];
            // Traverse the string
            for (int p = 0; p < len; p++) {
                // Update character frequency in the array based on the odd or even index
                if (p % 2 == 0) {
                    evenPosFreq[alpha.charAt(p)]++;
                } else {
                    oddPosFreq[alpha.charAt(p)]++;
                }
            }
            // to store max frequency of any character at even and odd positions
            int MaxFreqEven = 0, MaxFreqOdd = 0;
            // Find the maximum frequency
            for (char c = 'a'; c <= 'z'; c++) {
                MaxFreqEven = Math.max(MaxFreqEven, evenPosFreq[c]);
                MaxFreqOdd = Math.max(MaxFreqOdd, oddPosFreq[c]);
            }
            // Final result
            min_chars = min_chars - MaxFreqEven - MaxFreqOdd;
        }
        // For odd string
        else {
            // Get frequncy of all chars
            int[] allCharFreq = new int[128];
            for (int p = 0; p < len; p++) {
                allCharFreq[alpha.charAt(p)]++;
            }
            // Finding the most occurring character
            int maxChar = 0;
            for (char c = 'a'; c <= 'z'; c++) {
                maxChar = Math.max(maxChar, allCharFreq[c]);
            }
            // Final answer
            min_chars = min_chars - maxChar;
        }
        // return final answer
        return min_chars;
    }
    public static void main(String[] args) {
        String str = "tuto";
        System.out.print("The minimum numbers of character we should remove to get left and right rotation of string same is - "
                        + findMinCharRemoval(str));
    }
}

输出

The minimum numbers of character we should remove to get left and right rotation of string same is - 1

时间复杂度 – O（N），因为我们多次遍历字符串。

空间复杂度 – O（1），因为我们使用常数空间来存储字符串字符的频率。

我们学会了如何在Java中使字符串的左旋和右旋相同。程序员还可以尝试寻找给定字符串的左旋和右旋以进行更多练习。