Bigger is Greater

Problem

Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:

• It must be greater than the original word
• It must be the smallest word that meets the first condition

For example, given the word w = abcd, the next largest word is abdc.

Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer.

Function Description

Complete the biggerIsGreater function in the editor below. It should return the smallest lexicographically higher string possible from the given string or no answer.

biggerIsGreater has the following parameter(s):

• w: a string

Read more on the challenge page…

My Solution

I’m providing the solution for Python and JS, please leave on the comments if you found a better way.

The idea of the algorithm is quite simple, we need to modify the values of the array as far as possible to the right, that way we can guarantee the minimum increment.

The idea of the solution is a well-known algorithm which is already well explained in Wikipedia . Read the article if you want to know all the details.

I created however a chart that summarizes the procedure in a few steps and with an example:

def biggerIsGreater(w):
    w = list(w)
    # Find non-increasing suffix
    i = len(w)-1
    while i > 0 and w[i-1] >= w[i]:
        i -= 1

    if i <= 0:
        return 'no answer'

    # Find the rightmost successor to pivot in the suffix
    j = len(w) - 1
    while w[j] <= w[i - 1]:
        j -= 1
    
    # Swap the pivot with the rightmost character
    w[i-1], w[j] = w[j], w[i-1]

    # Reverse the sufix
    w[i:] = w[len(w)-1:i-1:-1]

    return ''.join(w)

function biggerIsGreater(w) {
    w = w.split('')
    // Find non-increasing suffix
    let i = w.length - 1;
    while (i > 0 && w[i - 1] >= w[i])
        i--;

    if (i <= 0)
        return 'no answer';
    
    // Find the rightmost successor to pivot in the suffix
    let j = w.length - 1;
    while (w[j] <= w[i - 1])
        j--;

    // Swap the pivot with the rightmost character
    const temp = w[i - 1];
    w[i - 1] = w[j];
    w[j] = temp;
    
    // Reverse suffix
    j = w.length - 1;
    while (i < j) {
        const temp = w[i];
        w[i] = w[j];
        w[j] = temp;
        i++;
        j--;
    }

    return w.join('');
}

Juan Cruz Martinez

¡Hola!

Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.