Lexicográficamente todas las substrings palindrómicas más cortas de una string dada

Dada una string s de tamaño N. La tarea es encontrar lexicográficamente todas las substrings palindrómicas más cortas de la string dada.

Ejemplos:

Entrada: s= “programación” 
Salida: agimnopr 
Explicación: 
La substring palíndromo lexicográfica más corta para la palabra “programación” serán los caracteres individuales de la string dada. Por lo tanto, la salida es: agimnop r.

Entrada: s= “geeksforgeeks” 
Salida: efgkors 

Enfoque: 
para resolver el problema mencionado anteriormente, la primera observación es que la substring palindrómica más corta será de tamaño 1. Entonces, según el enunciado del problema, tenemos que encontrar lexicográficamente todas las substrings distintas de tamaño 1, lo que significa que todos los caracteres en la string dada.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find Lexicographically all
// Shortest Palindromic Substrings from a given string
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all lexicographically
// shortest palindromic substring
void shortestPalindrome(string s)
{
 
    // Array to keep track of alphabetic characters
    int abcd[26] = { 0 };
 
    for (int i = 0; i < s.length(); i++)
        abcd[s[i] - 97] = 1;
 
    // Iterate to print all lexicographically shortest substring
    for (int i = 0; i < 26; i++) {
        if (abcd[i] == 1)
            cout << char(i + 97) << " ";
    }
}
 
// Driver code
int main()
{
    string s = "geeksforgeeks";
 
    shortestPalindrome(s);
 
    return 0;
}

// Java program to find Lexicographically all
// Shortest Palindromic Substrings from a given string
class Main
{
    // Function to find all lexicographically
    // shortest palindromic substring
    static void shortestPalindrome(String s)
    {
 
        // Array to keep track of
        // alphabetic characters
        int[] abcd = new int[26];
 
        for (int i = 0; i < s.length(); i++)
            abcd[s.charAt(i) - 97] = 1;
 
        // Iterate to print all lexicographically
        // shortest substring
        for (int i = 0; i < 26; i++)
        {
            if (abcd[i] == 1)
            {
                System.out.print((char)(i + 97) + " ");
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "geeksforgeeks";
        shortestPalindrome(s);
    }
}

# C++ program to find Lexicographically all
# Shortest Palindromic Substrings from a given string
 
# Function to find all lexicographically
# shortest palindromic substring
def shortestPalindrome (s) :
     
    # Array to keep track of alphabetic characters
    abcd = [0]*26
 
    for i in range(len(s)):
        abcd[ord(s[i])-97] = 1
     
    # Iterate to print all lexicographically shortest substring
    for i in range(26):
        if abcd[i]== 1 :
            print( chr(i + 97), end =' ' )
 
# Driver code
s = "geeksforgeeks"
 
shortestPalindrome (s)

// C# program to find Lexicographically
// all shortest palindromic substrings
// from a given string
using System;
 
class GFG{
     
// Function to find all lexicographically
// shortest palindromic substring
static void shortestPalindrome(string s)
{
 
    // Array to keep track of
    // alphabetic characters
    int[] abcd = new int[26];
 
    for(int i = 0; i < s.Length; i++)
       abcd[s[i] - 97] = 1;
 
    // Iterate to print all lexicographically
    // shortest substring
    for(int i = 0; i < 26; i++)
    {
       if (abcd[i] == 1)
       {
           Console.Write((char)(i + 97) + " ");
       }
    }
}
 
// Driver code
static public void Main(string[] args)
{
    string s = "geeksforgeeks";
    shortestPalindrome(s);
}
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript program to find Lexicographically all
// Shortest Palindromic Substrings from a given string
 
    // Function to find all lexicographically
    // shortest palindromic substring
    function shortestPalindrome(s)
    {
   
        // Array to keep track of
        // alphabetic characters
        let abcd = Array.from({length: 26}, (_, i) => 0);
   
        for (let i = 0; i < s.length; i++)
            abcd[s[i].charCodeAt()  - 97] = 1;
   
        // Iterate to print all lexicographically
        // shortest substring
        for (let i = 0; i < 26; i++)
        {
            if (abcd[i] == 1)
            {
                document.write(String.fromCharCode(i + 97)  + " ");
            }
        }
    }
 
// Driver Code
     
    let s = "geeksforgeeks";
    shortestPalindrome(s.split(''));
                
</script>

e f g k o r s

Complejidad de tiempo: O(N), donde N es el tamaño de la string.
Complejidad espacial: O(1)