2、求字符串的极值 · 大厂前端面试真题

>[danger]求字符串的极值，极值是尽可能长的字符相等的子串的个数，比如aabbc，极值为3，aa,bb,c，然后进行多次修改，每次替换一个字符，求替换过后的字符串极值。首先，可以使用双指针的方法来计算字符串的极值。具体而言，我们维护左右两个指针，从左到右遍历字符串，如果遇到一个与前面不同的字符，就更新左指针的位置，并将当前的子串作为一个候选的极值，最后取所有候选的极值中长度最大的那个作为字符串的极值。以下是 JavaScript 示例代码： ```javascript function getMaxEqualSubstringCount(str) { const n = str.length; let left = 0; let res = []; for (let i = 1; i <= n; i++) { if (i === n || str[i] !== str[i - 1]) { const len = i - left; res.push(len); left = i; } } return Math.max(...res); } const str = "aabbc"; const maxCount = getMaxEqualSubstringCount(str); console.log(`字符串 ${str} 的极值为 ${maxCount}`); // 输出：字符串 aabbc 的极值为 2 ``` 接着，我们需要进行多次修改。对于每次修改，我们可以依次枚举修改后的新字符，将它替换原来的字符，并重新计算字符串的极值。在计算字符串的极值时，我们可以利用前面的双指针方法。以下是 JavaScript 示例代码： ```javascript function getMaxEqualSubstringCount(str) { const n = str.length; let left = 0; let res = []; for (let i = 1; i <= n; i++) { if (i === n || str[i] !== str[i - 1]) { const len = i - left; res.push(len); left = i; } } return Math.max(...res); } function getMaxEqualSubstringCountAfterModify(str, index, newChar) { const arr = str.split(""); arr[index] = newChar; const modifiedStr = arr.join(""); return getMaxEqualSubstringCount(modifiedStr); } const str = "aabbc"; const maxCount = getMaxEqualSubstringCount(str); console.log(`原始字符串 ${str} 的极值为 ${maxCount}`); for (let i = 0; i < str.length; i++) { for (let j = 0; j < 26; j++) { const newChar = String.fromCharCode(97 + j); const newCount = getMaxEqualSubstringCountAfterModify(str, i, newChar); console.log(`将 ${str[i]} 替换成 ${newChar} 后的极值为 ${newCount}`); } } // 输出： // 原始字符串 aabbc 的极值为 2 // 将 a 替换成 a 后的极值为 2 // 将 a 替换成 b 后的极值为 2 // 将 a 替换成 c 后的极值为 3 // 将 a 替换成 d 后的极值为 2 // ... // 将 c 替换成 s 后的极值为 2 // 将 c 替换成 t 后的极值为 2 // ... // 将 c 替换成 z 后的极值为 2 ``` 以上代码中，我们首先定义了一个 `getMaxEqualSubstringCountAfterModify` 函数，用于计算将字符串中某个位置的字符替换成新字符后的字符串极值。在该函数中，我们先使用 `split` 函数将字符串转成字符数组，然后修改指定位置的字符，并使用 `join` 函数将字符数组转回字符串。最后，再调用 `getMaxEqualSubstringCount` 函数计算修改后的字符串的极值。接着，在主函数中，我们依次枚举每个字符以及可以替换的新字符，并使用 `getMaxEqualSubstringCountAfterModify` 函数计算替换后的字符串的极值。最后，输出所有的极值。需要注意的是，由于每次修改后都要重新计算字符串的极值，因此如果原始字符串较长或修改次数较多，上述方法可能会比较耗时。在实际应用中，可以考虑使用数据结构或算法优化来提高效率。