最长的子字符串，其中相邻的字符没有相邻的英文字母-C++-PHP中文网

最长的子字符串，其中相邻的字符没有相邻的英文字母

PHPz

发布： 2023-09-11 15:49:02

转载

919人浏览过

最长的子字符串，其中相邻的字符没有相邻的英文字母

在字符串操作领域，识别模式和提取有意义的子字符串是常见任务。一个有趣的问题涉及找到最长的子串，其中没有相邻字符是相邻的英文字母。在本文中，我们将使用 C++ 深入研究此问题的有效解决方案，并提供清晰的解释和示例测试用例。

问题陈述

给定一串小写英文字母，我们需要找到没有相邻字符是相邻英文字母的最长子串的长度。例如字符串“abacabx”中，满足该条件的最长子串为“abx”，长度为3。

方法和算法

为了解决这个问题，我们可以利用贪心方法。我们将迭代给定的字符串并检查当前字符和前一个字符是否是相邻的英文字母。如果是，我们将开始一个新的子字符串。否则，我们将扩展现有的子字符串。通过每当最长子串的长度超过之前的最大值时就更新它，我们就可以找到想要的结果。

C++ 实现

这是解决问题的 C++ 代码 &minus，

#include <iostream>
#include <string>
using namespace std;

int findLongestSubstring(const string& str) {
   int maxLength = 0;
   int currentLength = 1;
   
   for (int i = 1; i < str.length(); i++) {
      if (abs(str[i] - str[i - 1]) != 1) {
         currentLength++;
      } else {
         maxLength = max(maxLength, currentLength);
         currentLength = 1;
      }
   }
   
   maxLength = max(maxLength, currentLength);
    return maxLength;
}

int main() {
   string inputString = "abacabx";
   int longestSubstringLength = findLongestSubstring(inputString);
   
   cout << "Longest substring length: " << longestSubstringLength << endl;
   
   return 0;
}

登录后复制

输出

Longest substring length: 3

登录后复制

代码解释

函数 findLongestSubstring 接受输入字符串作为参数，并返回最长的不相邻英文字母字符的子字符串的长度。

我们将 maxLength 和 currentLength 分别初始化为 0 和 1。然后我们从第二个字符开始迭代字符串。如果当前字符与前一个字符之间的绝对差不等于 1，则增加 currentLength 以扩展当前子字符串。否则，如果当前长度超过之前的最大值，我们将更新 maxLength 并将 currentLength 重置为 1。