Рубрики

Подстрока максимальной четной длины, которая является перестановкой палиндрома

Учитывая строку задача состоит в том, чтобы найти максимальную длину подстроки это может быть организовано в палиндром (то есть, по крайней мере, одна из его перестановок — палиндром). Обратите внимание, что подстрока должна быть четной длины.

Примеры:

Input: str = “124565463”
Output: 6
“456546” is the valid sub-string

Input: str = “122313”
Output: 6

Подход: используйте две переменные: начало (включительно) и конец (исключение), чтобы отслеживать начальный и конечный индекс текущей подстроки, которая рассматривается в данной строке. Также используйте словарь с именем count, который хранит записи о том, сколько раз символ встречается в текущей подстроке. Теперь есть два возможных случая для подстроки:

  1. Если длина подстроки нечетна, то она не может быть учтена в конечном решении.
  2. Если длина подстроки является четной, то это может быть возможным решением, только если каждый символ в этой подстроке встречается четное количество раз, что можно сделать с помощью счетчика словаря. Мы проверяем, встречается ли каждый символ четное количество раз или нет. Если да, то мы включаем его как одно из возможных решений. Затем мы формируем следующую подстроку путем включения следующего символа в строку, что можно сделать, просто увеличивая end и проверяя рекурсивно, может ли быть сформирована подстрока большей длины, которая удовлетворяет заданным условиям и возвращает максимум из всех возможных решения.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ код для поиска максимальной длины
// подстрока (четной длины), которая может быть
// устроен в палиндром
#include <bits/stdc++.h>

using namespace std;

  

unordered_map<int, int> countt;

  
// функция, которая возвращает true, если данный
// подстрока может быть организована в палиндром

bool canBePalindrome(unordered_map<int, int> &countt) 

{

    for (auto key : countt)

    {

        if (key.second & 1) return false;

    }

    return true;

}

  
// Эта функция возвращает максимальную длину
// подстрока (четной длины), которая может быть
// устроен в палиндром

int maxPal(string str,

           unordered_map<int, int> &countt,

           int start, int end)

{

      

    // Если мы достигнем конца строки

    if (end == str.length()) 

    {

  

        // если строка имеет четную длину

        if ((end - start) % 2 == 0)

  

            // если строка может быть организована в

            // палиндром

            if (canBePalindrome(countt)) return end - start;

  

        return 0;

    

    else 

    {

  

        // четная подстрока

        if ((end - start) % 2 == 0) 

        {

  

            // Проверяем, может ли текущая подстрока быть

            // устроен в палиндром

            if (canBePalindrome(countt))

            {

                countt[str[end]]++;

                return max(end - start, maxPal(str, countt, 

                                               start, end + 1));

            

            else

            {

                countt[str[end]]++;

                return maxPal(str, countt, start, end + 1);

            }

        }

  

        // Подстрока нечетной длины

        else

        {

            countt[str[end]]++;

            unordered_map<int, int> c(countt.begin(), 

                                      countt.end());

            int length = maxPal(str, c, start, end + 1);

  

            countt[str[end]]--;

            countt[str[start]]--;

            return max(length, maxPal(str, countt, 

                                      start + 1, end));

        }

    }

}

  
// Код драйвера

int main(int argc, char const *argv[])

{

    string str = "124565463";

    int start = 0, end = 0;

  

    cout << maxPal(str, countt, start, end) << endl;

    return 0;

}

  
// Этот код предоставлен
// sanjeev2552

python3

# Python3 код для поиска максимальной длины подстроки
# (четной длины), которая может быть организована в палиндром

  

from collections import defaultdict

  
# функция, которая возвращает true, если данный
# подстрока может быть организована в палиндром

def canBePalindrome(count):    

    for key in count:

        if count[key] % 2 != 0:

            return False            

    return True

      
# Эта функция возвращает максимальную длину
# подстрока (четной длины), которая может быть
# устроен в палиндром

def maxPal(string, count, start, end):

      

    # Если мы достигнем конца строки

    if end == len(string):

  

        # если строка имеет четную длину

        if (end-start) % 2 == 0:

  

            # если строка может быть организована в

            # палиндром

            if canBePalindrome(count) == True:

                return end-start

                  

        return 0

          

    else:

          

        # Четная длина подстроки

        if (end-start) % 2 == 0:

              

            # Проверьте, может ли текущая подстрока быть

            # устроено в палиндром

            if canBePalindrome(count) == True:

                count[string[end]] += 1

                return max(end-start, maxPal(string, count, start, end + 1))

                  

            else:

                count[string[end]] += 1

                return maxPal(string, count, start, end + 1)

          

        # Нечетная длина подстроки

        else:

              

            count[string[end]] += 1

            length = maxPal(string, count.copy(), start, end + 1)

              

            count[string[end]] -= 1

            count[string[start]] -= 1

            return max(length, maxPal(string, count, start + 1, end))

              
# Код драйвера

string = '124565463'

start, end = 0, 0

count = defaultdict(lambda : 0)

  

print(maxPal(string, count, start, end))

Выход:

6

Рекомендуемые посты:

Подстрока максимальной четной длины, которая является перестановкой палиндрома

0.00 (0%) 0 votes