Contexto e objetivo

O problema de justificação de texto é amplamente utilizado em entrevistas de grandes empresas de tecnologia
(Google, Indeed, Coursera, Microsoft, Amazon, entre outras). A ideia central é transformar uma lista de
palavras em várias linhas, cada uma com exatamente maxWidth caracteres, de modo que as palavras fiquem
distribuídas de forma justa entre os espaços. A solução deve seguir uma abordagem greedy: preencher cada linha
com o maior número possível de palavras sem ultrapassar a largura máxima e, em seguida, distribuir os espaços
de forma tão uniforme quanto possível.

Existem regras claras sobre como tratar a última linha e também sobre o que acontece quando não é possível
distribuir os espaços com exatidão entre as palavras. Em linhas com mais de uma palavra, os espaços devem ser
distribuídos de forma que as lacunas à esquerda recebam mais espaços que as da direita, caso a divisão não seja
exata. A última linha, bem como linhas com apenas uma palavra, devem ficar à esquerda, sem inserção de
espaços extras entre as palavras.

Definições-chave

Antes de mergulhar no algoritmo, vamos consolidar algumas definições usadas ao longo da solução:

• Palavra: uma sequência de caracteres não espaços. Cada palavra tem comprimento maior que zero e não excede maxWidth.
• Linha: um conjunto de palavras cuja soma dos comprimentos dos próprios caracteres, mais os espaços entre as palavras, resulta exatamente em maxWidth.
• Última linha: a última linha do texto, que deve ser deixada com alinhamento à esquerda e sem espaços extras entre as palavras.
• Espaços: a quantidade de espaços entre as palavras de uma linha. Se a linha contiver mais de uma palavra, existem pelo menos um espaço entre cada par de palavras.

Para facilitar a visualização, imagine um conjunto de palavras com várias linhas resultantes à medida que seguimos a estratégia gulosa. Em cada linha, após selecionar as palavras que cabem, calculamos quantos espaços são necessários para alcançar o comprimento máximo, e distribuímos esses espaços entre as lacunas entre as palavras.

Exemplo ilustrativo (maxWidth = 15)

Considere um conjunto de palavras cuja contagem de caracteres por palavra é relevante para determinar quantas palavras cabem em cada linha. A cada passo, começamos com a palavra apontada pelo índice i (inicialmente, i aponta para a primeira palavra) e expandimos com o índice j para incluir palavras subsequentes, desde que a soma dos comprimentos das palavras e o mínimo de espaços entre elas não ultrapasse maxWidth.

Ao fim de cada linha, distinguimos entre dois modos de justificar:

• Se a linha possui apenas uma palavra ou for a última linha, realizamos uma justificativa à esquerda (leave-left), preenchendo o restante da linha com espaços à direita.
• Caso contrário, aplicamos a justificativa do meio (middle-justify): distribuímos os espaços de forma uniforme entre as lacunas. Se o número total de espaços não for divisível pelo número de lacunas, as lacunas à esquerda recebem mais espaços do que as da direita.

O processo é repetido até que todas as palavras sejam alocadas em linhas, sempre usando o critério guloso para maximizar o conteúdo de cada linha.

A seguir, um diagrama conceitual do fluxo:

// Pseudo-fluxo conceitual
i = 0
while i < n:
    j = i + 1
    lineLength = length(words[i])
    while j < n and lineLength + 1 + length(words[j]) <= maxWidth:
        lineLength += 1 + length(words[j])
        j += 1

    diff = maxWidth - lineLength
    wordsInLine = j - i

    if last line or wordsInLine == 1:
        // left justify
    else:
        // middle justify
    i = j

Lógica central do algoritmo (em termos práticos)

Para resolver o problema com clareza, algumas variáveis-chave aparecem naturalmente:

• i — índice inicial da linha atual (primeira palavra da linha).
• j — índice que aponta para a próxima palavra candidata a entrar na linha. O laço aumenta j até que a inclusão da palavra atual faça a linha ultrapassar maxWidth.
• lineLength — comprimento total atual da linha em termos de caracteres, somando apenas as palavras (sem contar os espaços extras entre as palavras).
• diff — quantidade de espaços totais que precisam ser distribuídos para chegar a maxWidth (diff = maxWidth - lineLength).
• spacesNeeded — número de lacunas entre palavras na linha atual. Se a linha contiver k palavras, há k-1 lacunas.
• spaces — número de espaços que cada lacuna receberá, quando distribuídos de forma uniforme (diff / spacesNeeded).
• extraSpaces — espaços restantes após a distribuição uniforme (diff % spacesNeeded), distribuídos para as lacunas da esquerda.

Para justificar a linha do meio (quando não é a última linha e não tem apenas uma palavra), construímos a linha como uma sequência de palavras intercaladas por espaços. Iniciamos com o mínimo de espaços entre as palavras (spaces), repetimos essa quantidade para cada lacuna, e, se houver espaços extras, aplicamos um espaço adicional aos primeiros pares de palavras (à esquerda).

Para a linha da esquerda (última linha ou contendo apenas uma palavra), mantemos apenas um espaço entre as palavras e preenchermos as lacunas restantes à direita com espaços em branco, para cumprir o comprimento máximo.

Esboço de implementação (narrativa em PT)

A ideia central de código para a solução envolve três partes bem separadas:

1. Construção das linhas: com i como início da linha, migração de j para cima, até que a linha atual não possa receber mais uma palavra sem exceder maxWidth. Ao final desse passo, temos i e j definindo a linha atual, com lineLength compensando apenas o tamanho das palavras.
2. Justificação da linha: dependendo de se a linha é a última ou tem apenas uma palavra, escolhemos left-justify ou middle-justify. Em cada caso, calculamos diff, spacesNeeded, spaces e extraSpaces, e então construímos a string final da linha.
3. Atualização de ponteiros: setamos i = j e repetimos o processo até o fim da lista de palavras.

Esboço de código (Pseudocódigo em PT)

// Função principal
entrada: palavras (array de strings), maxWidth (inteiro)
saída: linhas justificadas (array de strings)

i = 0
n = tamanho(palavras)
linhas = []

enquanto i < n:
    j = i + 1
    lineLength = comprimento(palavras[i])

    // tenta adicionar palavras na linha atual
    enquanto j < n e lineLength + 1 + comprimento(palavras[j]) <= maxWidth:
        lineLength += 1 + comprimento(palavras[j])
        j += 1

    diff = maxWidth - lineLength
    wordsInLine = j - i

    se (j == n) ou (wordsInLine == 1):
        linha = leftJustify(palavras, i, j, diff)
    senão:
        linha = middleJustify(palavras, i, j, diff)

    linhas.adicionar(linha)
    i = j

retornar linhas

// leftJustify(palavras, i, j, diff)
spacesRight = diff
linha = palavras[i]
para k de i+1 até j-1:
    linha += " " + palavras[k]
linha += " " * spacesRight
retornar linha

// middleJustify(palavras, i, j, diff)
spacesNeeded = (j - i) - 1
spaces = diff / spacesNeeded
extraSpaces = diff % spacesNeeded
linha = ''
for k de i até j-1:
    linha += palavras[k]
    se k < j-1:
        atualSpaces = spaces + (1 se extraSpaces > 0 else 0)
        linha += " " * atualSpaces
        se extraSpaces > 0: extraSpaces -= 1
retornar linha

Observação prática sobre o código acima:

• O passo de construção da linha usa i e j para delimitar as palavras que cabem naquela linha, garantindo que a soma de comprimentos das palavras e o mínimo de espaços entre elas não exceda maxWidth.
• A função leftJustify trata a linha com um único conjunto de palavras, ou a última linha, distribuindo espaços apenas à direita.
• A função middleJustify distribui espaços entre as lacunas de forma uniforme; se diff não for divisível pelo número de lacunas, os espaços extras são distribuídos para as lacunas da esquerda.

Análise de Complexidade

A estratégia descrita é anotada em termos de tempo e espaço, com foco no comportamento para grandes inputs:

• Tempo: O tempo é proporcional ao número de linhas multiplicado pelo comprimento máximo de cada linha (ou seja, O(L x maxWidth)), porque para cada linha formamos a string final com até maxWidth caracteres e, em cada linha, iteramos pelas palavras envolvidas para distribuir espaços. Em termos práticos, o processo de construção de cada linha envolve ler as palavras daquela linha e distribuir os espaços entre as lacunas.
• Espaço: A saída final já armazena as linhas resultantes; além disso, a construção de cada linha usa espaço adicional proporcional ao maxWidth. Assim, a complexidade de espaço adicional é O(L x maxWidth), onde L é o número de linhas e maxWidth é a largura da linha.

Essa análise reforça a ideia de que o método é eficiente para textos moderados a grandes, mantendo a complexidade viável para a maioria dos casos de uso práticos de formatação de texto em display de interfaces.

Casos de teste e considerações práticas

Para assegurar a robustez da implementação, alguns cenários devem ser verificados com cuidado:

• Última linha com várias palavras: deve ficar à esquerda, com o restante preenchido com espaços à direita.
• Linha com apenas uma palavra: deve ficar à esquerda, sem espaços entre palavras, com o espaço restante preenchendo à direita.
• Distribuição desigual de espaços: quando diff não é divisível por spacesNeeded, as lacunas mais à esquerda recebem os espaços adicionais.
• Validação de fronteiras: quando i aponta para a última palavra, j pode ficar igual a i+1 ou maior, dependendo do espaço disponível; o caso final deve ser tratado como última linha.
• Condição de entrada: o array de palavras contém pelo menos uma palavra e cada palavra tem comprimento entre 1 e maxWidth.

Boas práticas de teste incluem: cenários com largura máxima muito pequena em relação ao comprimento de palavras, cenários com muitos espaços distribuídos, e cenários com várias linhas onde a distribuição de espaços muda entre linhas diferentes, garantindo que a lógica de left vs middle justify seja sólida.

Consolidação e melhores práticas

Contemplar esse problema sob a ótica de um programador sênior envolve, além de entender as regras, pensar na clareza de código, na modularidade e em testes consistentes. A separação em funções distintas para left-justify e middle-justify facilita manutenção e evolução do algoritmo. Mesmo que a ideia central seja simples — colocar o maior número de palavras por linha e distribuir espaços — a implementação exige atenção aos detalhes de contagem de espaços, distribuição desigual e tratamento da última linha.

Um bom texto de referência incorpora esses elementos com explicações claras, exemplos comentados e um esqueleto de código que possa ser testado de forma incremental. A prática de manter o estado com ponteiros i e j ajuda a tornar o algoritmo intuitivo, reduzindo o risco de bugs em casos de borda.

Além disso, vale a pena considerar extensões futuras, como suporte a tabulações, caracteres multibyte ou um modo de configuração que permita escolher entre diferentes políticas de distribuição de espaços (por exemplo, favorecer o centro ao invés da esquerda em certo contexto visual). A ideia central, no entanto, permanece fiel ao modelo descrito: justiça de distribuição de espaços com uma distribuição preferencial para as lacunas da esquerda quando necessário, sempre preservando as regras do último linha e de linhas com apenas uma palavra.