将字符串左旋转和右旋转相匹配的JavaScript程序以最小化改变的字符

在这个问题中，我们需要确定使字符串的左旋转和右旋转相同的最小成本。

下面是我们用来解决问题的观察结果。

• 对于长度为奇数的字符串，所有字符都应该相等，以使左旋转和右旋转相同。

• 长度为偶数的字符串的偶数和奇数索引处的字符应该相同。

  问题陈述 - 我们有一个包含不同字符的大小为N的字符串。我们需要确定通过改变给定字符串的字符使其左旋转和右旋转相同的最小成本。更改字符串中任何字符的成本为1。

  注意 - 字符串的左旋转将字符串向左方向移动1个位置，并将第一个字符放在字符串的末尾。

字符串的右旋转将字符串向右方向移动1个位置，并将第一个字符放在字符串的开头。

示例示例

输入

str = ‘tut’

输出

‘1’

解释 - 由于字符串的长度是奇数，我们需要使所有字符相同。所以，我们需要将’u’改为’t’。

输入

‘gggggggggggg’

输出

0

说明 - 由于字符串的所有字符都相同，我们不需要改变任何字符。

输入

str = "mpmntrmnfdmn";

输出

5

解释 - 由于字符串长度是偶数，我们需要使所有偶数索引和奇数索引的字符相等。在偶数索引上，我们可以将所有字符都设为’m’，在奇数索引上，我们可以将所有字符都设为’n’。

方法1

在这个方法中，我们将使奇数长度的字符串中的所有字符相等，并使偶数长度的字符串中偶数索引和奇数索引上的字符相等。

我们可以找到奇数长度的字符串中频率最高的字符，并将所有字符都设为它。此外，我们还可以找到在偶数和奇数位置上频率最高的字符，并相应地更改偶数和奇数索引上的字符。

算法

步骤1 - 使用字符串的长度初始化变量’str_size’。

步骤2 - 定义变量’minCost’，用于存储改变字符以使左右旋转相等的最小成本。

步骤3 - 如果’str_size’ % 2等于零，我们需要按照下面的步骤进行。

步骤3.1 - 定义大小为128的evenFreq和oddFreq数组变量，并将所有数组元素初始化为零。

步骤3.2 - 遍历字符串，并使用charCodeAt()方法获取字符的ASCII值。如果当前索引是偶数，则在evenFreq数组中更新字符频率。否则，在oddFreq数组中更新字符频率。

步骤3.3 - 在获取偶数索引和奇数索引上每个字符的频率之后，我们需要找到频率最高的字符。因此，声明maxiEven和maxiOdd变量。

步骤3.4 - 从数组中找到最大值，并将它们存储在maxiEven和maxiOdd变量中。

步骤3.5 - 将字符串长度减去maxiEven和maxiOdd，并将结果赋给minCost变量。

步骤4 - 对于奇数长度的字符串，我们应该按照以下步骤进行。

步骤4.1 - 定义charFreq数组以存储字符串的所有字符的频率。

步骤4.2 - 遍历字符串并更新数组中字符的频率。

步骤4.3 - 从数组中找到最大值。

步骤4.4 - 将字符串长度减去maxFreq，并将结果赋给minCost。

步骤5 - 返回minCost的值。

示例

function findMinCharacters(str) {
    var str_size = str.length;  
    // Base case if all characters are different in a given string
    var minCost = str_size;  
    // For even size of strings
    if (str_size % 2 === 0) {
      // Defining array to store the frequency
      var evenFreq = new Array(128).fill(0);
      var oddFreq = new Array(128).fill(0);
        // Traverse the string
      for (var p = 0; p < str_size; p++) {
        if (p % 2 === 0) {
          // Update character frequency in the array based on the odd or even index
          evenFreq[str[p].charCodeAt(0)]++;
        } else {
          oddFreq[str[p].charCodeAt(0)]++;
        }
      }
      var maxiEven = 0;
      var maxiOdd = 0;
        for (var c = "a".charCodeAt(0); c <= "z".charCodeAt(0); c++) {
        maxiEven = Math.max(maxiEven, evenFreq[c]);
        maxiOdd = Math.max(maxiOdd, oddFreq[c]);
      }
        // Final answer
      minCost = minCost - maxiEven - maxiOdd;
    }
      // For the odd length of string
    else {
      var charFreq = new Array(128).fill(0);  
      // store character frequency in the array
      for (var p = 0; p < str_size; p++) {
        charFreq[str[p].charCodeAt(0)]++;
      }  
      // Finding the maximum frequency of any character
      var maxFreq = 0;
      for (var c = "a".charCodeAt(0); c <= "z".charCodeAt(0); c++) {
        maxFreq = Math.max(maxFreq, charFreq[c]);
      }
     // Final answer
      minCost = minCost - maxFreq;
    }

    //   returning the answer
    return minCost;
  }  
  var str = "tut";
  console.log(
    "The minimum number of characters we should remove to get a left and right rotation of string same is - " +
      findMinCharacters(str)
  );

输出结果

The minimum number of characters we should remove to get a left and right rotation of string same is - 1

时间复杂度为O(N)，因为我们遍历长度为N的字符串。

空间复杂度为O(N)，因为我们使用了常数空间。

从这个问题的解决方案中，我们可以了解到每个问题并没有特定的解决方法。有时候，我们需要观察问题的输入和输出，并基于此解决问题。