Longest Valid Parentheses

Q: Existe uma solução de programação dinâmica para o problema dos parênteses válidos mais longos?

Sim. Seja end[i] o comprimento da maior substring bem-formada que termina no índice i ; seu valor é 0 quando s[i] é ( . Se s[i-1] for ( , então end[i] = end[i-2] + 2 . Se for ) , observe j = i - end[i-1] - 1 , o caractere antes da sequência que termina em i-1 : quando s[j] for ( , ele envolve essa sequência, e end[i] = end[i-1] + 2 + end[j-1] , em que o último termo se junta a uma sequência adjacente à sua esquerda. A resposta é o maior end[i] , com tempo e memória O(n) .

DifícilPilha Programação dinâmica

+10

Você recebe uma string s formada apenas pelos caracteres ( e ). Encontre a substring mais longa (uma sequência de caracteres consecutivos) que esteja bem formada: cada ( nela é fechada por um ) posterior também nela, e os pares são aninhados corretamente, como em (()()). Retorne o comprimento dessa substring ou 0 quando nem mesmo () aparecer.

Função

longestValidParentheses(s: string) → integer

sstring: uma string de caracteres ( e )
Retornainteger: o comprimento da maior substring bem formada, ou 0 se não houver nenhuma

Restrições

1 ≤ s.length ≤ 6 × 10⁴
Cada caractere de s é ( ou ).

Exemplos

Entrada: s = "()(())"
Saída: 6
Explicação: A string inteira está bem formada: () seguida por (()). Duas partes bem formadas lado a lado formam uma única parte bem formada, então a resposta são todos os 6 caracteres.

Entrada: s = "())((())"
Saída: 4
Explicação: O ) no índice 2 não tem par, então nenhuma resposta pode atravessá-lo, e o ( no índice 3 nunca é fechado. O trecho mais longo é (()) do índice 4 ao 7, com comprimento 4, que é maior que o () no início.

Entrada: s = "))(("
Saída: 0
Explicação: Os dois ) vêm antes dos dois (, então nenhum ( é fechado. Nenhuma substring está bem formada e a resposta é 0.

+21 testes ocultos ao enviar

Para ir além

Você também pode informar onde começa a substring bem formada mais longa, escolhendo a mais à esquerda quando várias tiverem o mesmo comprimento?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Duas coisas tornam isso mais difícil do que verificar uma única string. Trechos bem-formados se juntam quando se encostam, então () e (()) lado a lado contam como uma sequência de 6. E um caractere solto, como o ) em ())(()), interrompe a string, de modo que nenhuma resposta pode atravessá-lo. Testar cada início custa O(n²). A solução é lembrar onde a sequência atual começou: uma pilha de índices com um marcador de base no fundo faz isso em uma única passagem, e duas passagens de contadores simples fazem isso sem nenhuma pilha.

Expanda uma substring a partir de cada posição inicial

Correta, mas não termina nos maiores testes

Intuição

Percorra uma substring da esquerda para a direita mantendo um saldo que aumenta em 1 para ( e diminui em 1 para ). A substring está bem formada exatamente quando o saldo nunca fica abaixo de 0 e termina em 0. Ficar abaixo de 0 significa que um ) apareceu sem nada aberto para fechar.

Então, fixe um início e percorra para a direita, atualizando o saldo um caractere por vez. Toda vez que ele volta a 0, o trecho do início até aqui está bem formado, e você registra seu comprimento. No momento em que ele fica abaixo de 0, pare: esse ) permanece sem correspondência em qualquer trecho mais longo a partir desse início. Toda substring bem formada tem algum início, e você tenta todos os finais para ela, então nada passa despercebido.

O custo é o problema. Em uma string com 59998 ( seguidos por (), o saldo nunca fica abaixo de 0, então, para cada início, a varredura vai até o fim: cerca de n²/2 = 1.8 × 10^9 passos para n = 6 × 10^4. Os testes grandes são construídos assim. (Verificar cada substring do zero, em vez de aumentá-la, seria ainda pior, O(n³).)

Algoritmo

Defina best como 0.
Para cada início, defina balance como 0 e percorra o fim do início até o último caractere.
Some 1 para ( e subtraia 1 para ).
Se balance for menor que 0, pare este início. Se for 0, atualize best com o comprimento do trecho end - start + 1.
Retorne best.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Pilha de índices com um marcador de base

Intuição

Combinar parênteses usando uma pilha é algo familiar: empilhe cada (, remova um para cada ). Aqui você também precisa dos comprimentos, então empilhe índices e mantenha um índice extra na base da pilha: a base, a posição logo antes do trecho em que você está. No início, nada foi lido, então a base é -1.

Em (, empilhe seu índice. Em ), remova um índice. Duas coisas podem acontecer. Se a pilha agora estiver vazia, você removeu a base, então esse ) não tinha nada para fechar. Nenhuma substring bem formada pode contê-lo, e ele se torna a nova base: empilhe seu índice. Caso contrário, o índice que ficou no topo é o último caractere antes do trecho que termina em i: ou um ( que ainda está aberto ou a base. Tudo depois dele até i está combinado, e o trecho não pode alcançar mais à esquerda, então seu comprimento é i - top.

Aqui está ())((()):

i = 0, (: empilhe 0. Pilha [-1, 0].
i = 1, ): remova 0. O topo é -1, então o trecho é 1 - (-1) = 2.
i = 2, ): remova -1 e a pilha fica vazia. Esse ) não tem par, então empilhe 2 como a nova base. Pilha [2].
i = 3, 4, 5, três (: empilhe-os. Pilha [2, 3, 4, 5].
i = 6, ): remova 5. O topo é 4, então o trecho é 6 - 4 = 2.
i = 7, ): remova 4. O topo é 3, então o trecho é 7 - 3 = 4, a resposta.

A base é o que permite que trechos adjacentes se juntem. Em ()(()), o primeiro par mede 1 - (-1) = 2, e o último ) remove o índice 2 e encontra -1 no topo novamente, então mede 5 - (-1) = 6. Medir a partir do ( correspondente daria 4 e deixaria de fora o () no início. Cada índice é empilhado e removido no máximo uma vez, então a passagem é O(n), e a pilha pode conter até n+1 índices.

Algoritmo

Inicie uma pilha contendo -1 e defina best como 0.
Para cada índice i, empilhe i se s[i] for (.
Se for ), desempilhe uma vez.
Se a pilha estiver vazia agora, empilhe i como a nova base. Caso contrário, atualize best com i - top.
Retorne best.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Conte as aberturas e os fechamentos em duas passagens

Intuição

A pilha só informa onde a execução atual começou. Dois contadores também podem fazer isso. Percorra da esquerda para a direita contando opens e closes desde a última redefinição. Quando forem iguais, tudo desde a redefinição está bem formado, com comprimento 2 × closes. Quando closes fica à frente, um ) não tem par, no mesmo momento em que a pilha perdeu sua base; então, redefina ambos os contadores para 0.

Uma passagem não é suficiente. Um ( que nunca fecha mantém opens à frente para sempre, e as contagens nunca mais se igualam. Em ((), a passagem da esquerda termina com 2 aberturas e 1 fechamento e não encontra nada, embora () esteja bem ali. Então, percorra uma segunda vez, da direita para a esquerda, com os papéis invertidos: redefina quando opens fica à frente. Lida de trás para a frente, (() dá um fechamento, depois uma abertura (iguais: comprimento 2), e então uma abertura que provoca a redefinição. A resposta é o maior valor entre as duas passagens.

Por que duas passagens encontram todas as sequências: a sequência mais longa é delimitada por caracteres que nunca podem ser correspondidos, ou pelas extremidades da string. Se o limite esquerdo for um ) sem par ou o início, a passagem da esquerda redefine os contadores exatamente onde a sequência começa e percebe quando eles se igualam onde ela termina. Se o limite esquerdo for um ( sem par, o limite direito não pode ser um ), pois esse ) fecharia o ( sem par e a sequência seria mais longa. Portanto, o limite direito é um ( sem par ou o fim, e a passagem da direita encontra a sequência da mesma forma. Cada passagem percorre a string uma vez usando dois inteiros, então o tempo é O(n) e a memória extra é O(1).

Algoritmo

Defina best como 0, e opens e closes como 0.
Percorra da esquerda para a direita, contando cada caractere. Quando as contagens forem iguais, atualize best com 2 × closes. Quando closes for maior, redefina ambos para 0.
Redefina ambos os contadores e, em seguida, percorra da direita para a esquerda da mesma maneira, exceto que você os redefinirá quando opens for maior.
Retorne best.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Armadilhas e casos extremos

A maioria das respostas erradas conta os pares corretos nos lugares errados ou perde o início de uma sequência.

Contar os pares correspondentes na string inteira. ())((()) tem 3 pares, mas eles não estão todos lado a lado, e a resposta é 4, não 6.
Medir uma sequência a partir do ( correspondente. Em ()(()), o último ) corresponde ao índice 2, o que resulta em 4 e deixa de fora o () que vem antes. Meça a partir do índice que fica na pilha após a remoção.
Começar com uma pilha vazia. O primeiro ) de ()) não tem então nada com que comparar, e um ) sem correspondência remove um elemento de uma pilha vazia. A base -1 corrige ambos os problemas.
Executar os contadores em apenas uma direção. (() retorna 0 da esquerda para a direita, e ()) retorna 0 da direita para a esquerda; a resposta é 2 para ambos.
Zerar os contadores quando eles são iguais. Contagens iguais significam que a sequência ainda pode crescer, como em ()(); zere apenas quando um lado ficar à frente.
Em Lua e R, as posições começam em 1, então a primeira base é 0, não -1.

Perguntas frequentes4

Qual é a complexidade de tempo de Longest Valid Parentheses?

Tanto a solução com pilha quanto a solução com contador em duas passagens leem cada caractere um número constante de vezes, portanto são executadas em tempo O(n). A pilha precisa de memória O(n) no pior caso, como em uma string composta apenas por (, enquanto os contadores precisam de O(1). Testar cada posição inicial tem complexidade O(n²).

Por que a pilha começa com -1?

O comprimento da sequência é o índice atual menos o índice imediatamente anterior ao início da sequência. Para uma sequência que começa no índice 0, esse índice anterior é -1, uma posição antes da string. Empurrar -1 primeiro significa que a pilha nunca fica vazia quando um ) correspondente mede o comprimento e, quando um ) sem correspondência o remove da pilha, esse ) passa a ser a nova base.

Existe uma solução de programação dinâmica para o problema dos parênteses válidos mais longos?

Sim. Seja end[i] o comprimento da maior substring bem-formada que termina no índice i; seu valor é 0 quando s[i] é (. Se s[i-1] for (, então end[i] = end[i-2] + 2. Se for ), observe j = i - end[i-1] - 1, o caractere antes da sequência que termina em i-1: quando s[j] for (, ele envolve essa sequência, e end[i] = end[i-1] + 2 + end[j-1], em que o último termo se junta a uma sequência adjacente à sua esquerda. A resposta é o maior end[i], com tempo e memória O(n).

Por que uma única passagem com contadores não é suficiente?

Uma varredura da esquerda para a direita só é reiniciada quando ) supera (. Um ( extra que nunca é fechado mantém as contagens diferentes pelo resto da string, então a varredura nunca as vê se igualarem. Em ((), ela termina com 2 parênteses de abertura e 1 de fechamento e não encontra nada. Ler da direita para a esquerda trata o ( solto da mesma forma que a primeira varredura trata um ) solto, então as duas varreduras juntas cobrem todas as sequências.

Python

def longestValidParentheses(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "()(())"

Esperado

Longest Valid Parentheses

Função

Restrições

Exemplos

Dicas

Solução

Expanda uma substring a partir de cada posição inicial

Pilha de índices com um marcador de base

Conte as aberturas e os fechamentos em duas passagens

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos