Início / coding / Perguntas / 79295066
Accepted
CodeCrusader
Asked: 2024-12-20 00:59:51 +0800 CST

encontre o número de subsequências que são maiores que outra string

  • 772

Dadas duas sequências s de comprimento m e outra sequência t de comprimento n, conte quantas subsequências de s são maiores que t

Uma sequência p é chamada maior que outra sequência q se ela satisfaz os casos abaixo:

a) p[i] > q[i] na primeira posição onde p e q diferem, ou
b) |p| > |q| e q é um prefixo de p (onde |p| denota o comprimento da senha p).

Exemplo:

s = "bab" t = "ab"

Resultado = 5

Explicação:

Valid subsequences of s which are greater than t are
"b"
"ba"
"bb"
"bab"
"b"

restrições: comprimento de s 1 a 10^5 comprimento de t 1 a 100

O comprimento de t pode ser maior que o comprimento de s também com combinações válidas.

Resolvi isso usando uma abordagem recursiva, mas está levando uma complexidade de tempo O(2^n * n).

public class Main {
    private static final int MOD = 1_000_000_007;

    private static void subsequence(String s, int index, String current, List<String> subsequences) {
        if (index == s.length()) {
            if (!current.isEmpty()) {
                subsequences.add(current);
            }
            return;
        }
        subsequence(s, index + 1, current, subsequences);
        subsequence(s, index + 1, current + s.charAt(index), subsequences);
    }

    private static boolean isGreater(String s1, String t) {
        int len1 = s1.length();
        int len2 = t.length();
        for (int i = 0; i < Math.min(len1, len2); i++) {
            if (s1.charAt(i) > t.charAt(i)) {
                return true;
            } else if (s1.charAt(i) < t.charAt(i)) {
                return false;
            }
        }
        return len1 > len2;
    }

    public static int solve(String s, String t) {
        List<String> subsequences = new ArrayList<>();
        subsequence(s, 0, "", subsequences);

        int count = 0;
        for (String e : subsequences) {
            if (isGreater(e, t)) {
                count = (count + 1) % MOD;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(solve("aba", "ab")); // Expected: 3
        System.out.println(solve("bab", "ab")); // Expected: 5
        System.out.println(solve("wrrmkhds", "bebbjvcgzlwtbvasphvm")); // Expected: 255
        System.out.println(solve("o", "h"));   // Expected: 1
    }
}

Como isso pode ser resolvido em menos complexidade de tempo?

java

2 respostas

  1. Parece que você pode simplesmente criar uma lista auxiliar com os índices das letras que são menores que t[i]. Chame essa lista de x.

    Em seguida, use matemática simples para determinar quantas subsequências você pode formar usando os intervalos entre os índices em x.

    No seu exemplo, x=[1]. Então, temos o primeiro intervalo fechado [0-0]que pode formar 1subsequência. O segundo intervalo é [2-2], que nos dá o intervalo [0-2]. Você pode formar 3C1+3C2+3C3=6subsequências, mas terá que subtrair as subsequências para [0-0](já contado) e [1-1](não incluído). Então, isso nos dá 1+4=5subsequências.

    • 1
  2. Best Answer

    Você pode usar uma relação de recorrência e implementá-la com programação dinâmica.

    Se considerarmos um sufixo de 𝑠, começando no índice 𝑖 e um sufixo de 𝑡, começando no índice 𝑗 (vamos usar a notação 𝑠[𝑖:] e 𝑡[𝑗:] para esses sufixos), então temos um problema menor para resolver, ou seja, quantas subsequências do primeiro sufixo são maiores que o segundo sufixo. Podemos usar esse resultado para o problema maior.

    Se quisermos saber a solução para 𝑠[𝑖:] e 𝑡[𝑗:], então temos alguns cenários:

    • Se 𝑠[𝑖:] estiver vazio (ou seja, 𝑖 ≥ 𝑚), então há 0 subsequências.

    • Caso contrário, podemos dividir a contagem de subsequências em dois grupos:

      1. Subsequências que excluem 𝑠[𝑖]

        Esta contagem é igual à solução para 𝑠[𝑖+1:] e 𝑡[𝑗:] (nós apenas removemos 𝑠[𝑖] da entrada)

      2. Subsequências que incluem 𝑠[𝑖]

        • Se 𝑗 ≥ 𝑛 ou 𝑠[𝑖] > 𝑡[𝑗], então os seguintes caracteres de 𝑡 não importam mais, e podemos escolher livremente quais caracteres de 𝑠[𝑖+1:] incluir ou não. Isso representa 2 𝑚-1-𝑖 subsequências possíveis, todas começando com 𝑠[𝑖].

        • Quando 𝑠[𝑖] = 𝑡[𝑗], então a contagem de subsequências é dada pela solução para 𝑠[𝑖+1:] e 𝑡[𝑗+1:]

        • Caso contrário (quando 𝑠[𝑖] < 𝑡[𝑗]), fizemos uma escolha inválida e, portanto, há 0 subsequências para contar neste cenário.

    Mais formalmente, defina 𝑚 como o comprimento de 𝑠, 𝑛 como o comprimento de 𝑡 e 𝑇 𝑖, 𝑗 como o número de subsequências de 𝑠[𝑖:] que são maiores que 𝑡[𝑗:]. Então:

    • 𝑇 𝑖, 𝑗 = 0, quando 𝑖 ≥ 𝑚

    • 𝑇 𝑖, 𝑗 = 𝑇 𝑖+1, 𝑗 + 2 𝑚-1-𝑖 , quando de outra forma 𝑗 ≥ 𝑛 ou 𝑠[𝑖] > 𝑡[𝑗]

    • 𝑇 𝑖, 𝑗 = 𝑇 𝑖+1, 𝑗 + 𝑇 𝑖+1, 𝑗+1 , quando de outra forma 𝑠[𝑖] = 𝑡[𝑗]

    • 𝑇 𝑖, 𝑗 = 0, caso contrário

    No final, precisamos do valor para 𝑇 0, 0

    Para implementar isso, poderíamos usar uma abordagem de baixo para cima, começando com um sufixo vazio de 𝑠 (ou seja, 𝑖 = 𝑚) e, então, aumentar esse sufixo (diminuindo 𝑖). Para cada sufixo, considere 𝑗 diminuindo de 𝑛 para 0. Como 𝑇 𝑖, 𝑗 depende diretamente apenas de 𝑇 𝑖+1, 𝑗 e 𝑇 𝑖+1, 𝑗+1 , na verdade não precisamos armazenar toda essa matriz 𝑇, mas podemos ser suficientes mantendo duas linhas consecutivas dessa matriz apenas na memória.

    Aqui está uma implementação:

        public static int solve(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        int[] dp = new int[n+1];
        int[] dpPrev;
        
        for (int i = m - 1; i >= 0; i--) { // Grow the suffix of s that is considered
            // Take a copy to have a reference to previous results (for smaller s suffix)
            dpPrev = dp.clone(); 
            // There are 2^(length of s[i:]) - 1 non-empty subsequences 
            //     when t[j:] is empty (j == n):
            dp[n] = 2 * dp[n] + 1;
            // Add the cases where s[i] is included in the subsequences
            for (int j = n - 1; j >= 0; j--) {
                int cmp = Character.compare(s.charAt(i), t.charAt(j));
                       // Add the count of all subsequences of s[s+1:] (+1 for empty one)
                dp[j] += cmp >  0 ? dpPrev[n] + 1 
                       // Add the count of subsequences of s[i+1:] greater than t[j+1:]
                       : cmp == 0 ? dpPrev[j+1]
                       : 0;
            }
        } 
        return dp[0];
    }

    NB: seu código tinha uma constante 1_000_000_007, que não foi mencionada na sua pergunta. Imagino que não será problema para você incorporar o requisito relacionado a essa constante. Preferi mantê-la de fora para focar na pergunta.

    • 1

relate perguntas