Siguiente palabra que no contiene un palíndromo y tiene caracteres de la primera k

Dada una string y un límite k, encuentre lexicográficamente la siguiente palabra que contenga caracteres de un conjunto de primeras K letras del alfabeto inglés y no contenga un palíndromo ya que es una substring de longitud superior a uno. Se puede suponer que la string de entrada no contiene una substring palindrómica.

Ejemplos: 

Input : s = "cba" 
        k = 4
Output : cbd

Input : s = "cba"
        k = 3
Output : -1
we can't form such word

Enfoque: nuestro objetivo es formar lexicográficamente la siguiente palabra, por lo que debemos movernos de derecha a izquierda. Mientras se desplaza de derecha a izquierda, cambie el último alfabeto de la derecha. Al incrementar el último alfabeto, asegúrese de que la string formada contenga las primeras k letras y no contenga ninguna substring como palíndromo.

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

// CPP program to find lexicographically
// next word which contains first K
// letters of the English alphabet
// and does not contain a palindrome
// as it's substring of length more
// than one.
#include <bits/stdc++.h>
using namespace std;
 
// function to return lexicographically
// next word
void findNextWord(string s, int m)
{
    // we made m as m+97 that means
    // our required string contains
    // not more than m+97(as per ASCII
    // value) in it.
    m += 97;
    int n = s.length();
    int i = s.length() - 1;
     
    // increment last alphabet to make
    // next lexicographically next word.
    s[i]++;
 
    while (i >= 0 && i <= n - 1) {
         
        // if i-th alphabet not in first
        // k letters then make it as "a"
        // and then increase (i-1)th letter
        if (s[i] >= m) {
            s[i] = 'a';
            s[--i]++;
        }
 
        // to check whether formed string
        // palindrome or not.
        else if (s[i] == s[i - 1] ||
                 s[i] == s[i - 2])
            s[i]++;
 
        // increment i.
        else
            i++;
    }
 
    // if i less than or equals to one
    // that means we not formed such word.
    if (i <= -1)
        cout << "-1";
    else
        cout << s;
}
 
// Driver code for above function.
int main()
{
    string str = "abcd";
    int k = 4;
    findNextWord(str, k);
    return 0;
}

// Java program to find lexicographically
// next word which contains first K
// letters of the English alphabet
// and does not contain a palindrome
// as it's substring of length more
// than one.
 
public class GFG
{
 
    // function to return lexicographically
    // next word
    static void findNextWord(char[] s, int m)
    {
        // we made m as m+97 that means
        // our required string contains
        // not more than m+97(as per ASCII
        // value) in it.
        m += 97;
        int n = s.length;
        int i = s.length - 1;
 
        // increment last alphabet to make
        // next lexicographically next word.
        s[i]++;
 
        while (i >= 0 && i <= n - 1)
        {
 
            // if i-th alphabet not in first
            // k letters then make it as "a"
            // and then increase (i-1)th letter
            if (s[i] >= m)
            {
                s[i] = 'a';
                s[--i]++;
            }
            // to check whether formed string
            // palindrome or not.
            else if (s[i] == s[i - 1]
                    || s[i] == s[i - 2])
            {
                s[i]++;
            }
            // increment i.
            else
            {
                i++;
            }
        }
 
        // if i less than or equals to one
        // that means we not formed such word.
        if (i <= -1)
        {
            System.out.println("-1");
        }
        else
        {
            System.out.println(s);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char[] str = "abcd".toCharArray();
        int k = 4;
        findNextWord(str, k);
    }
}
 
// This code contributed by Rajput-Ji

# Python3 program to find lexicographically
# next word which contains first K
# letters of the English alphabet and
# does not contain a palindrome as it's
# substring of length more than one.
 
# Function to return lexicographically next word
def findNextWord(s, m):
 
    # we made m as m+97 that means
    # our required string contains
    # not more than m+97(as per ASCII
    # value) in it.
    m += 97
    n = len(s)
    i = len(s) - 1
     
    # increment last alphabet to make
    # next lexicographically next word.
    s[i] = chr(ord(s[i]) + 1)
 
    while i >= 0 and i <= n - 1:
         
        # if i-th alphabet not in first
        # k letters then make it as "a"
        # and then increase (i-1)th letter
        if ord(s[i]) >= m:
            s[i] = 'a'
            i -= 1
            s[i] = chr(ord(s[i]) + 1)
 
        # to check whether formed string
        # palindrome or not.
        elif s[i] == s[i - 1] or s[i] == s[i - 2]:
            s[i] = chr(ord(s[i]) + 1)
 
        # increment i.
        else:
            i += 1
     
    # if i less than or equals to one
    # that means we not formed such word.
    if i <= -1:
        print("-1")
    else:
        print(''.join(s))
 
# Driver code
if __name__ == "__main__":
 
    string = "abcd"
    k = 4
    findNextWord(list(string), k)
 
# This code is contributed by Rituraj Jain

// C# program to find lexicographically
// next word which contains first K
// letters of the English alphabet
// and does not contain a palindrome
// as it's substring of length more
// than one.
using System;
 
class GFG
{
 
    // function to return lexicographically
    // next word
    static void findNextWord(char[] s, int m)
    {
        // we made m as m+97 that means
        // our required string contains
        // not more than m+97(as per ASCII
        // value) in it.
        m += 97;
        int n = s.Length;
        int i = s.Length - 1;
 
        // increment last alphabet to make
        // next lexicographically next word.
        s[i]++;
 
        while (i >= 0 && i <= n - 1)
        {
 
            // if i-th alphabet not in first
            // k letters then make it as "a"
            // and then increase (i-1)th letter
            if (s[i] >= m)
            {
                s[i] = 'a';
                s[--i]++;
            }
            // to check whether formed string
            // palindrome or not.
            else if (s[i] == s[i - 1] ||
                     s[i] == s[i - 2])
            {
                s[i]++;
            }
             
            // increment i.
            else
            {
                i++;
            }
        }
 
        // if i less than or equals to one
        // that means we not formed such word.
        if (i <= -1)
        {
            Console.WriteLine("-1");
        }
        else
        {
            Console.WriteLine(s);
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        char[] str = "abcd".ToCharArray();
        int k = 4;
        findNextWord(str, k);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find lexicographically
// next word which contains first K
// letters of the English alphabet
// and does not contain a palindrome
// as it's substring of length more
// than one.
 
// function to return lexicographically
// next word
function findNextWord(s, m)
{
    // we made m as m+97 that means
    // our required string contains
    // not more than m+97(as per ASCII
    // value) in it.
    m += 97;
    var n = s.length;
    var i = s.length - 1;
     
    // increment last alphabet to make
    // next lexicographically next word.
    s[i] = String.fromCharCode(s[i].charCodeAt(0)+1);
 
    while (i >= 0 && i <= n - 1) {
         
        // if i-th alphabet not in first
        // k letters then make it as "a"
        // and then increase (i-1)th letter
         
        if (s[i].charCodeAt(0) >= m) {
 
            s[i] = 'a';
            s[i-1] = String.fromCharCode(s[i-1].charCodeAt(0)+1);
            i--;
        }
 
        // to check whether formed string
        // palindrome or not.
        else if (s[i] == s[i - 1] ||
                 s[i] == s[i - 2])
            s[i] = String.fromCharCode(s[i].charCodeAt(0)+1);
 
        // increment i.
        else
            i++;
    }
 
    // if i less than or equals to one
    // that means we not formed such word.
    if (i <= -1)
        document.write( "-1");
    else
        document.write( s.join(''));
}
 
// Driver code for above function.
var str = "abcd".split('');
var k = 4;
findNextWord(str, k);
 
// This code is contributed by noob2000.
</script>

abda

Complejidad de tiempo: O(N) , donde N representa la longitud de la string dada.
Espacio auxiliar: O(1) , no se requiere espacio adicional, por lo que es una constante.