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

Опубликовано: 24 Января, 2022

Дана строка строчных английских алфавитов. Задача - проверить, существует ли в строке подпоследовательность, не являющаяся палиндромом. Если есть хотя бы 1 подпоследовательность, не являющаяся палиндромом, выведите YES, иначе выведите NO.
Примеры :

 Ввод : str = "abaab"
Выход : ДА
Подпоследовательности «ab», «abaa» или «aab» не являются палиндромом.

Ввод : str = "zzzz"
Выход : НЕТ
Все возможные подпоследовательности - палиндромы.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

The main observation is that if the string contains at least two distinct characters, then there will always be a subsequence of length at least two which is not a palindrome. Only if all the characters of the string are the same then there will not be any subsequence that is not a palindrome. Because in an optimal way we can choose any two distinct characters from a string and place them in same order one after each to form a non-palindromic string.
Below is the implementation of above approach:

C++

// C++ program to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
bool isAnyNotPalindrome(string s)
{
    // use set to count number of
    // distinct characters
    set<char> unique;
 
    // insert each character in set
    for (int i = 0; i < s.length(); i++)
        unique.insert(s[i]);
 
    // If there is more than 1 unique
    // characters, return true
    if (unique.size() > 1)
        return true;
    // Else, return false
    else
        return false;
}
 
// Driver code
int main()
{
    string s = "aaaaab";
 
    if (isAnyNotPalindrome(s))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

Java

// Java program to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
 
import java.util.*;
class GFG
{
     
    // Function to check if there exists
    // at least 1 sub-sequence in a string
    // which is not palindrome
    static boolean isAnyNotPalindrome(String s)
    {
        // use set to count number of
        // distinct characters
        Set<Character> unique=new HashSet<Character>();
     
        // insert each character in set
        for (int i = 0; i < s.length(); i++)
            unique.add(s.charAt(i));
     
        // If there is more than 1 unique
        // characters, return true
        if (unique.size() > 1)
            return true;
        // Else, return false
        else
            return false;
    }
     
    // Driver code
    public static void main(String []args)
    {
        String s = "aaaaab";
     
        if (isAnyNotPalindrome(s))
            System.out.println("YES");
        else
            System.out.println("NO");
     
    }
}

Python3

# Python3 program to check if there exists
# at least 1 sub-sequence in a string
# which is not palindrome
 
 
# Function to check if there exists
# at least 1 sub-sequence in a string
# which is not palindrome
def isAnyNotPalindrome(s):
 
    # use set to count number of
    # distinct characters
    unique=set()
 
    # insert each character in set
    for i in range(0,len(s)):
        unique.add(s[i])
 
    # If there is more than 1 unique
    # characters, return true
    if (len(unique) > 1):
        return True
         
    # Else, return false
    else:
        return False
 
 
# Driver code
if __name__=="__main__":
    s = "aaaaab"
 
    if (isAnyNotPalindrome(s)):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by
# ihritik

C#

// C# program to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
using System;
using System.Collections.Generic;
 
class GFG
{
     
    // Function to check if there exists
    // at least 1 sub-sequence in a string
    // which is not palindrome
    static bool isAnyNotPalindrome(String s)
    {
        // use set to count number of
        // distinct characters
        HashSet<char> unique=new HashSet<char>();
     
        // insert each character in set
        for (int i = 0; i < s.Length; i++)
            unique.Add(s[i]);
     
        // If there is more than 1 unique
        // characters, return true
        if (unique.Count > 1)
            return true;
        // Else, return false
        else
            return false;
    }
     
    // Driver code
    public static void Main(String []args)
    {
        String s = "aaaaab";
     
        if (isAnyNotPalindrome(s))
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
 
// Function to check if there exists
// at least 1 sub-sequence in a string
// which is not palindrome
function isAnyNotPalindrome(s)
{
    // use set to count number of
    // distinct characters
    var unique = new Set();
 
    // insert each character in set
    for (var i = 0; i < s.length; i++)
        unique.add(s[i]);
 
    // If there is more than 1 unique
    // characters, return true
    if (unique.size > 1)
        return true;
    // Else, return false
    else
        return false;
}
 
// Driver code
var s = "aaaaab";
if (isAnyNotPalindrome(s))
    document.write( "YES");
else
    document.write( "NO");
 
 
</script>

Output:

YES

Сложность времени: O (N), где N - длина строки.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

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

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ