C++ 可以使用范围在L和R之间的字符创建的字符串的最大长度回文字符串

回文字符串是正向和逆向读取相同的字符串。一个回文字符串的例子是Mam。在本教程中，我们使用C++编程来预定义字符的范围，以找到字符串的最大长度回文字符串。

我们的任务是找到使用输入字符串的最大长度回文字符串。我们定义字符的范围来生成该字符串。根据情况，L和R可以取任何值。

示例1

String = “amem”
Range = {1,4}

输出

在上面的示范中，输入字符串是“amem”，构成回文字符串的范围是{1, 4}。该范围定义了回文字符串的起始和结束字符。利用该范围，最长的回文字符串的长度为3，这些字符串是mem或mam。

示例2

String = “bbbb”
Range = {1, 4}

输出

在上述输入字符串中，定义范围内的最长回文字符串长度为4。该回文字符串是bbbb。

C++库函数在示例中使用

语法

memset()： 这个标准库函数在<cstring>头文件中定义。它将内存块设置为特定的值。它复制这些值。它有3个参数：ptr，val和num。ptr是起始地址指针，val是要设置的值，num是要设置的数量。

memset(ptr, val, num);

size() : 该库函数被定义在<std>头文件中。它返回字符串的大小。

string_name.size();

向量（Vector）： 这个库函数在<vector>头文件中定义。它是C++中的一个动态数组。当添加或删除元素时，它会自动调整数组的大小。

vector<data_type> vector_name;

步骤

获取一个输入字符串。
使用一个计数器变量计算字符在范围内的频率。
找到奇数频率和偶数频率。
最长回文字符串的长度是奇数频率减去1和偶数频率的和。
打印结果。

示例1

我们使用C++编程语言实现了其中一个演示。用户定义的函数计算奇数和偶数频率。将偶数和奇数减去1的频率相加以计算在定义范围内回文字符串的最大长度。

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

//user-defined function to calculate frequencies
int calculateQueries(int m, int s, int p[N][26])
{
    m--;
    s--;

    // marking for odd frequency
    bool f = false;

    // counter variable to count the maximum length
    int cnt = 0;

    // Traversing all characters
    for (int x = 0; x < 26; x++) 
    {
        int cnt1 = p[s][x];
        if (m > 0)
            cnt1 -= p[m - 1][x];

        // finding odd frequencies
        if (cnt1 % 2 == 1) 
        {
            f = true;
            cnt += cnt1 - 1;
        }

        else
            cnt += cnt1;
    }

    if (f)
        cnt += 1;

    return cnt;
}

void calculateFreq(string str, int p[N][26])
{
    int m = str.size();

    // Iteration for counter variable
    for (int x = 0; x < m; x++)
    {
        p[x][str[x] - 'a']++;
    }

    for (int x = 1; x < m; x++)
    {
        for (int y = 0; y < 26; y++)
            p[x][y] += p[x - 1][y];
    }
}

// Code controller
int main()
{
    string str = "bbbbb";

    // prefix array
    int p[N][26];
    memset(p, 0, sizeof p);
    calculateFreq(str, p);

    int q[][2] = { 1, 4};
    int sq = sizeof(q) / sizeof(q[0]);

    for (int x = 0; x < sq; x++)
    {
        cout << calculateQueries(q[x][0],
                               q[x][1], p)
             << endl;
    }

    return 0;
}

输出

示例2

我们使用C++编程概念实现了一个演示。使用向量来计算回文字符的频率。创建一个用户定义的函数maxLengthPalindrome()来找到在{1, 4}之间的回文字符串的所需长度。

您可以根据需要更改输入字符串和范围。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxLengthPalindrome(string& s, int st, int e) 
{
    // Initialize a vector to store the frequency of each character
    vector<int> freq(26, 0);

    // Count the frequency of characters within the given range
    for (int x = st - 1; x <= e - 1; x++)
    {
        freq[s[x] - 'a']++;
    }

    int l = 0;
    bool oddFreq = false;

    // Calculate the maximum length palindrome
    for (int x = 0; x < 26; x++)
    {
        l += freq[x] / 2 * 2;

        if (freq[x] % 2 == 1) 
        {
            oddFreq = true;
        }
    }

    // If there is a character with an odd frequency, increment the length by 1
    if (oddFreq) 
    {
        l++;
    }

    return l;
}

int main() 
{
    string s = "amem";
    int st = 1;
    int e = 4;

    int maxLen = maxLengthPalindrome(s, st, e);

    cout << "Maximum length palindrome: " << maxLen << endl;

    return 0;
}