Рубрики

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

Учитывая строку, подсчитайте, сколько палиндромов максимальной длины присутствует (это не должно быть подстрокой)
Примеры:

Input : str = "ababa"
Output: 2
Explanation : 
palindromes of maximum of lenghts are  :
 "ababa", "baaab" 

Input : str = "ababab"
Output: 4
Explanation : 
palindromes of maximum of lenghts are  :
 "ababa", "baaab", "abbba", "babab"

Подход Палиндром может быть представлен как «str + t + reverse (str)» .
Примечание : «t» пусто для палиндромных струн четной длины.

Подсчитайте, сколько способов можно сделать «str», а затем умножьте на «t» (количество пропущенных одиночных символов).

Пусть c i будет количеством появлений символа в строке. Рассмотрим следующие случаи:
1. Если c i четно. Тогда половина каждого максимального палиндрома будет содержать ровно буквы f i = c i / 2.
2. Если c i нечетно. Тогда половина каждого максимального палиндрома будет содержать ровно буквы f i = (c i — 1) / 2.

Пусть k будет числом нечетных c i . Если k = 0, максимальная длина палиндромов будет четной; в противном случае это будет нечетно и будет ровно k возможных средних букв, т. е. мы можем установить эту букву в середине палиндрома.

Число перестановок из n объектов с n 1 одинаковыми объектами типа 1, n 2 идентичных объектов типа 2 ,, и n3 идентичных объектов типа 3 равно n! / (n1! * n2! * n3!) .
Итак, здесь мы имеем общее количество символов в виде f a + f b + f a + ……. + F y + f z . Итак, число перестановок равно (f a + f b + f a + ……. + F y + f z +)! / ф а ! f b !… f y ! f z !.

Теперь, если K не равно 0, очевидно, что ответом является k * (f a + f b + f a + ……. + F y + f z +)! / ф а ! f b !… f y ! f z !

Ниже приведена реализация вышеперечисленного.

C ++

// C ++ реализация для подсчета
// максимальная длина палиндромов
#include <bits/stdc++.h>

using namespace std;

  
// факториал числа

int fact(int n)

{

    int ans = 1;

    for (int i = 1; i <= n; i++)    

        ans = ans * i;

    return (ans);

}

  
// функция для подсчета максимальной длины палиндромов.

int numberOfPossiblePallindrome(string str, int n)

{   

    // Подсчитать количество вхождений

    // фрахтователя в строке

    unordered_map<char, int> mp;

    for (int i = 0; i < n; i++) 

        mp[str[i]]++;

  

    int k = 0;  // Количество синглов

    int num = 0;  // числитель результата

    int den = 1;  // знаменатель результата

    int fi;  

    for (auto it = mp.begin(); it != mp.end(); ++it)

    {

        // если частота четная

        // fi = ci / 2

        if (it->second % 2 == 0) 

            fi = it->second / 2;

          

        // если частота нечетная

        // fi = ci - 1/2.

        else 

        {

            fi = (it->second - 1) / 2; 

            k++;

        }

  

        // сумма всех частот

        num = num + fi; 

          

        // произведение факториала

        // каждая частота

        den = den * fact(fi); 

    }

      

    // если все символы уникальны

    // так что не будет никакого паллиндрома,

    // так что если num! = 0, то только мы

    // найти факториал

    if (num != 0) 

        num = fact(num);

          

    int ans = num / den; 

      

    if (k != 0)

    {

        // k - единственный

        // элементы, которые могут быть

        // помещен посередине

        ans = ans * k;

    }

      

    return (ans);

}

  
// Драйвер программы

int main()

{

    char str[] = "ababab";

    int n = strlen(str);

    cout << numberOfPossiblePallindrome(str, n);

    return 0;

}

Джава

// Java-реализация для подсчета
// максимальная длина палиндромов

import java.util.*;

  

class GFG

{

  
// факториал числа

static int fact(int n)

{

    int ans = 1;

    for (int i = 1; i <= n; i++) 

        ans = ans * i;

    return (ans);

}

  
// функция для подсчета максимальной длины палиндромов.

static int numberOfPossiblePallindrome(String str, int n)

    // Подсчитать количество вхождений

    // фрахтователя в строке

    Map<Character,Integer> mp = new HashMap<>();

    for (int i = 0; i < n; i++) 

        mp.put( str.charAt(i),mp.get( str.charAt(i))==null?

                1:mp.get( str.charAt(i))+1);

  

    int k = 0; // Количество синглов

    int num = 0; // числитель результата

    int den = 1; // знаменатель результата

    int fi; 

    for (Map.Entry<Character,Integer> it : mp.entrySet()) 

    {

        // если частота четная

        // fi = ci / 2

        if (it.getValue() % 2 == 0

            fi = it.getValue() / 2;

          

        // если частота нечетная

        // fi = ci - 1/2.

        else

        {

            fi = (it.getValue() - 1) / 2

            k++;

        }

  

        // сумма всех частот

        num = num + fi; 

          

        // произведение факториала

        // каждая частота

        den = den * fact(fi); 

    }

      

    // если все символы уникальны

    // так что не будет никакого паллиндрома,

    // так что если num! = 0, то только мы

    // найти факториал

    if (num != 0

        num = fact(num);

          

    int ans = num / den; 

      

    if (k != 0)

    {

        // k - единственный

        // элементы, которые могут быть

        // помещен посередине

        ans = ans * k;

    }

      

    return (ans);

}

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

public static void main(String[] args)

{

    String str = "ababab";

    int n = str.length();

    System.out.println(numberOfPossiblePallindrome(str, n));

}
}

  
// Этот код предоставлен Принчи Сингхом

python3

# Реализация Python3 для подсчета
# максимальная длина палиндромов

import math as mt

  
# факториал числа

def fact(n):

    ans = 1

    for i in range(1, n + 1): 

        ans = ans * i

    return (ans)

  
# функция для подсчета максимальной длины палиндромов.

def numberOfPossiblePallindrome(string, n):

      

    # Подсчет количества вхождений

    # фрахтователя в строке

    mp = dict()

    for i in range(n):

        if string[i] in mp.keys():

            mp[string[i]] += 1

        else

            mp[string[i]] = 1

  

    k = 0 # Количество синглов

    num = 0 # числитель результата

    den = 1 # знаменатель результата

    fi = 0

    for it in mp:

      

        # если частота четная

        # fi = ci / 2

        if (mp[it] % 2 == 0):

            fi = mp[it] // 2

          

        # если частота нечетная

        # fi = ci - 1/2.

        else:

          

            fi = (mp[it] - 1) // 2

            k += 1

  

        # сумма всех частот

        num = num + fi 

          

        # произведение факториала

        # каждая частота

        den = den * fact(fi) 

      

    # если все символы уникальны

    # так что не будет никакого паллиндрома,

    # так что если num! = 0, то только мы

    # поиск факториала

    if (num != 0): 

        num = fact(num)

          

    ans = num //den 

      

    if (k != 0):

      

        # k являются единственными

        # элементов, которые могут быть

        # посередине

        ans = ans * k

      

    return (ans)

  
Код водителя

string = "ababab"

n = len(string)

print(numberOfPossiblePallindrome(string, n))

  
# Этот код предоставлен
# Мохит Кумар 29

C #

// C # реализация для подсчета
// максимальная длина палиндромов

using System;

using System.Collections.Generic;

      

class GFG

{

  
// факториал числа

static int fact(int n)

{

    int ans = 1;

    for (int i = 1; i <= n; i++) 

        ans = ans * i;

    return (ans);

}

  
// функция для подсчета максимальной длины палиндромов.

static int numberOfPossiblePallindrome(String str, int n)

    // Подсчитать количество вхождений

    // фрахтователя в строке

    Dictionary<char,int> mp = new Dictionary<char,int>();

    for (int i = 0 ; i < n; i++)

    {

        if(mp.ContainsKey(str[i]))

        {

            var val = mp[str[i]];

            mp.Remove(str[i]);

            mp.Add(str[i], val + 1); 

        }

        else

        {

            mp.Add(str[i], 1);

        }

    }

  

    int k = 0; // Количество синглов

    int num = 0; // числитель результата

    int den = 1; // знаменатель результата

    int fi; 

    foreach(KeyValuePair<char, int> it in mp)

    {

        // если частота четная

        // fi = ci / 2

        if (it.Value % 2 == 0) 

            fi = it.Value / 2;

          

        // если частота нечетная

        // fi = ci - 1/2.

        else

        {

            fi = (it.Value - 1) / 2; 

            k++;

        }

  

        // сумма всех частот

        num = num + fi; 

          

        // произведение факториала

        // каждая частота

        den = den * fact(fi); 

    }

      

    // если все символы уникальны

    // так что не будет никакого паллиндрома,

    // так что если num! = 0, то только мы

    // найти факториал

    if (num != 0) 

        num = fact(num);

          

    int ans = num / den; 

      

    if (k != 0)

    {

        // k - единственный

        // элементы, которые могут быть

        // помещен посередине

        ans = ans * k;

    }

      

    return (ans);

}

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

public static void Main(String[] args)

{

    String str = "ababab";

    int n = str.Length;

    Console.WriteLine(numberOfPossiblePallindrome(str, n));

}
}

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


Выход:

4

Сложность времени: O (n)

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

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

0.00 (0%) 0 votes