C++ 找到字符串S中的最大偶数值子字符串

在这个问题中，我们需要找到给定字符串的最大偶数值子字符串。偶数字符串总是以2、4、6、8、0结尾。因此，我们可以取给定字符串的所有子字符串，如果任何子字符串是偶数且大于最大子字符串，则可以更新最大子字符串的值。

问题描述： 我们有一个只包含数字的字符串str。我们需要找到str中的最大子字符串，该子字符串是一个偶数值。

示例：

输入：

str = "1234789"

输出

123478

解释 - 最长的偶数子串是123478.

输入

str = ‘3208’

输出

3208

说明 - 字符串已经是偶数。因此，它打印字符串本身。

输入

str = "13579";

输出

‘Not Possible’

解释 - 该字符串不包含任何偶数子串。因此，它打印了“不可能”。

方法1

在这个方法中，我们将遍历给定字符串的所有子字符串。如果子字符串的最后一个字符可以被2整除，则意味着该字符串是偶数。之后，我们将检查当前字符串是否大于最大字符串。如果是，则替换最大字符串。

算法

步骤1 - 将“largeEven”字符串初始化为空字符串。

步骤2 - 使用for循环从第0个索引开始遍历字符串。在循环内部，初始化“temp”字符串，并使用嵌套循环从第p个索引开始遍历字符串。

步骤3 - 从索引处取出字符，并将其附加到“temp”字符串中。

步骤4 - 如果字符串的最后一个字符可以被2整除，则执行getMaxStr()函数以找到最大字符串，并将其返回的值存储到largeEven字符串中。

步骤4.1 - 在getMaxStr()函数中，如果第一个字符串的长度大于第二个字符串的长度，则返回第一个字符串。否则，返回第二个字符串。

步骤4.2 - 如果两个字符串的长度相同，则使用循环开始匹配字符串的所有字符。

步骤4.3 - 如果第一个字符串中的第p个索引处的字符大于第二个字符串中的字符，则返回第一个字符串。否则，返回第二个字符串。如果相同索引处的字符相同，则继续下一次迭代。

步骤5 - 返回“largeEven”字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string getMaxStr(string num1, string num2) {
    // Comparing the size of both strings
    if (num1.length() > num2.length()){
        return num1;
    } else if (num1.length() < num2.length()) {
        return num2;
    }
    // For the same length of strings
    for (int p = 0; p < num1.length(); ++p) {
        if (num1[p] > num2[p])
            return num1;
        else if (num1[p] < num2[p])
            return num2;
    }
    // If strings are equal
    return num1;
}
string findStr(string str) {
    // string size
    int len = str.size();
    string largeEven = "";
    // get all substrings of the string
    for (int p = 0; p < len; p++) {
        string temp = "";
        for (int q = p; q < len; q++) {
            temp += str[q];
            int tempLen = temp.size();
            // check if the substring is even
            if ((temp[tempLen - 1] - '0') % 2 == 0)
            {
                // Get maximum string
                largeEven = getMaxStr(largeEven, temp);
            }
        }
    }
    return largeEven;
}
int main() {
    string str = "1234789";
    string result = findStr(str);
    if (result == ""){
        cout << "Not possible";
    } else {
        cout << "The largest possible even number is " << result << "\n";
    }
    return 0;
}

输出

The largest possible even number is 123478

时间复杂度 – O(N*N), 因为我们得到给定字符串的所有子串。

空间复杂度 – O(N) 用于存储子字符串。

方法二

在这种方法中，我们将从字符串的末尾开始遍历，找到第一个偶数数字的出现。我们可以将从第0个索引到当前数字的子字符串作为字符串的最后一个数字是偶数。

算法

步骤1 - 将 ‘index’ 变量初始化为 -1，以存储从末尾开始的第一个偶数数字的索引。

步骤2 - 从末尾开始遍历字符串。

步骤3 - 如果当前数字能被2整除，将 ‘index’ 变量的值更新为 ‘I’ 并停止循环。

步骤4 - 如果 ‘index’ 的值为 -1，返回一个空字符串，因为字符串只包含奇数数字。否则，返回从第0个索引开始，并且长度为 ‘index + 1’ 的子字符串。

例子

#include <bits/stdc++.h>
using namespace std;

string findStr(string str) {
    int len = str.length();
    int index = -1;
    // Traverse string from right to left
    for (int i = len - 1; i >= 0; i--) {
        // Getting the first even digit from the right
        if ((str[i] - '0') % 2 == 0) {
            index = i;
            break;
        }
    }
    if (index == -1)
        return "";
    else
        return str.substr(0, index + 1);
}
int main(){
    string str = "1234879";
    string result = findStr(str);
    if (result == "") {
        cout << "Not possible";
    } else {
        cout << "The largest possible even number is " << result << "\n";
    }
    return 0;
}

输出

The largest possible even number is 12348

时间复杂度 – O（N）反向遍历字符串或获取子字符串。

空间复杂度 – O（1），因为我们不使用额外的空间。

第一种方法是朴素的方法，第二种方法是优化的方法。在第二种方法中，我们使用了偶字符串的最后一位数字可被2整除的逻辑，并且由于我们是从最后开始遍历，所以可以得到最大长度的子字符串。