Рубрики

Самая длинная непалиндромная подстрока

Дана строка размером n. Задача состоит в том, чтобы найти длину самой большой подстроки, которая не является палиндромом.

Примеры:

Input : abba 
Output : 3
Here maximum length non-palindromic substring is
'abb' which is of length '3'. There could be other
non-palindromic sub-strings also of length three 
like 'bba' in this case.

Input : a
Output : 0

Простое решение — рассмотреть каждую подстроку и проверить, является ли она палиндромом или нет . Наконец, верните длину самой длинной непалиндромной подстроки.

Эффективное решение основано на подходе ниже.

Check for the case where all characters of
the string are same or not.
    If yes, then answer will be '0'.
Else check whether the given string of size 
'n' is palindrome or not. 
    If yes, then answer will be 'n-1'
Else answer will be 'n' 

C ++

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

using namespace std;

  
// служебная функция для проверки
// строка палиндром или нет

bool isPalindrome(string str)

{

    // Проверка на палиндром.

    int n = str.size();

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

        if (str.at(i) != str.at(n-i-1))

            return false;

  

    // палиндромная строка

    return true;

}

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

int maxLengthNonPalinSubstring(string str)

{

    int n = str.size();

    char ch = str.at(0);

  

    // проверить все ли символы

    // строки одинаковые или нет

    int i = 1;

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

        if (str.at(i) != ch)

            break;

  

    // Все символы одинаковы, мы не можем

    // сделать непалиндромную строку.

    if (i == n)

        return 0;

  

    // Если строка является палиндромом, мы можем сделать

    // это не палиндром, удалив любой

    // угловой персонаж

    if (isPalindrome(str))

        return n-1;

  

    // Полная строка не является палиндромом.

    return n;

}

  
// Программа драйвера для тестирования выше

int main()

{

    string str = "abba";

    cout << "Maximum length = "

         << maxLengthNonPalinSubstring(str);

    return 0;

}

Джава

// Реализация Java, чтобы найти максимальную длину
// подстрока, которая не является палиндромом

public class GFG

{

    // служебная функция для проверки

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

    static Boolean isPalindrome(String str)

    {

        int n = str.length();

  

        // Проверка на палиндром.

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

            if (str.charAt(i) != str.charAt(n-i-1))

                return false;

  

        // палиндромная строка

        return true;

    }

  

    // функция для поиска максимальной длины

    // подстрока, которая не является палиндромом

    static int maxLengthNonPalinSubstring(String str)

    {

        int n = str.length();

        char ch = str.charAt(0);

  

        // проверить все ли символы

        // строки одинаковые или нет

        int i = 1;

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

            if(str.charAt(i) != ch)

                break;

  

        // Все символы одинаковы, мы не можем

        // сделать непалиндромную строку.

        if (i == n)

            return 0;

  

        // Если строка является палиндромом, мы можем сделать

        // это не палиндром, удалив любой

        // угловой персонаж

        if (isPalindrome(str))

            return n-1;

  

        // Полная строка не является палиндромом.

        return n;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        String str = "abba";

        System.out.println("Maximum Length = "

             + maxLengthNonPalinSubstring(str));

    }

}
// Этот код предоставлен Sumit Ghosh

Python 3

# Реализация Python 3, чтобы найти максимум
# длина подстроки, которая не является палиндромом

  
# служебная функция для проверки
# строка палиндром или нет

def isPalindrome(str):

      

    # Проверьте на палиндром.

    n = len(str)

    for i in range(n // 2):

        if (str[i] != str[n - i - 1]):

            return False

  

    # строка палиндрома

    return True

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

def maxLengthNonPalinSubstring(str):

    n = len(str)

    ch = str[0]

  

    # проверить все ли символы

    # строки одинаковы или нет

    i = 1

    for i in range(1, n):

        if (str[i] != ch):

            break

  

    # Все персонажи одинаковы, мы не можем

    # сделать непалиндромную строку.

    if (i == n):

        return 0

  

    # Если строка является палиндромом, мы можем сделать

    # это непалиндром, удалив любой

    # угловой символ

    if (isPalindrome(str)):

        return n - 1

  

    # Полная строка не является палиндромом.

    return n

  
Код водителя

if __name__ == "__main__":

      

    str = "abba"

    print("Maximum length ="

           maxLengthNonPalinSubstring(str))

  
# Этот код предоставлен ita_c

C #

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

using System;

  

class GFG {

      

    // служебная функция для проверки

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

    static bool isPalindrome(String str)

    {

        int n = str.Length;

  

        // Проверка на палиндром.

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

            if (str[i] != str[n - i - 1])

                return false;

  

        // палиндромная строка

        return true;

    }

  

    // функция для поиска максимальной длины

    // подстрока, которая не является палиндромом

    static int maxLengthNonPalinSubstring(String str)

    {

        int n = str.Length;

        char ch = str[0];

  

        // проверить все ли символы

        // строки одинаковые или нет

        int i = 1;

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

            if(str[i] != ch)

                break;

  

        // Все символы одинаковы, мы не можем

        // сделать непалиндромную строку.

        if (i == n)

            return 0;

  

        // Если строка - палиндром, мы можем

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

        // любой угловой символ

        if (isPalindrome(str))

            return n-1;

  

        // Полная строка не является палиндромом.

        return n;

    }

  

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

    public static void Main()

    {

        String str = "abba";

        Console.Write("Maximum Length = "

                      + maxLengthNonPalinSubstring(str));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// Реализация PHP, чтобы найти максимальную длину
// подстрока, которая не является палиндромом

  
// служебная функция для проверки
// строка палиндром или нет

function isPalindrome($str)

{

    $n = strlen($str);

  

    // Проверка на палиндром.

    for ($i = 0; $i < $n / 2; $i++)

        if ($str[$i] != $str[$n - $i - 1])

            return false;

  

    // палиндромная строка

    return true;

}

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

function maxLengthNonPalinSubstring($str)

{

    $n = strlen($str);

    $ch = $str[0];

  

    // проверить все ли символы

    // строки одинаковые или нет

    $i = 1;

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

        if($str[$i] != $ch)

            break;

  

    // Все символы одинаковы, мы не можем

    // сделать непалиндромную строку.

    if ($i == $n)

        return 0;

  

    // Если строка - палиндром, мы можем

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

    // любой угловой символ

    if (isPalindrome($str))

        return ($n - 1);

  

    // Полная строка не является палиндромом.

    return $n;

}

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

$str = "abba";

echo "Maximum Length = ",

      maxLengthNonPalinSubstring($str);

  
// Этот код предоставлен ajit
?>


Выход:

Maximum length = 3

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

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Самая длинная непалиндромная подстрока

0.00 (0%) 0 votes