Ten program polega na znalezieniu liczby podciągów z przynajmniej i wyraźnymi literami, w których 1 <= i <= 26 łańcucha d długości N.

def DistinctChars (N, S):
    # Write your code here
    substrings = " ".join((S[i:j] for i in range(N) for j in range(i+1, N+1)))
    for i in range(1, 27):
        if i==1:
            yield len(substrings.split(" "))
        else:
            yield len([item for item in substrings.split(" ") if len(set(item)) >= i])
    
 
N = int(input())
S = input()
 
out_ = DistinctChars(N, S)
print (' '.join(map(str, out_)))

Przykładowe wejście

N = 4.

A = AABC.

wyjście

10 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Kod jest szybki w razie potrzeby, a wyjście jest poprawne. Ale bez względu na to, czego próbowałem, przekroczyła przydzieloną pamięć o 250 MB.

0
Joshy Joy 21 marzec 2021, 13:12

1 odpowiedź

Najlepsza odpowiedź

Myślę, że limit pamięci jest przekroczony, ponieważ wszystkie substrings są przechowywane w jednej zmiennej. Zamiast tego możesz zdefiniować pętlę, aby wstępnie obliczyć wartości len(set(item)) w kodzie:

def DistinctChars (N, S):
    
    all_U = []
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_U.append(len(D))
    
    for i in range(1, 27):
        yield sum( 1 for n in all_U if n>=i)

Takie podejście może zapisać zasoby wykładniczo, ponieważ wszystkie substrings są zastępowane tylko liczbą unikalnych znaków.

Ps. Zdałem sobie sprawę, że w rzeczywistości możliwe jest zbudowanie jeszcze bardziej wydajnego algorytmu, gdzie liczba substringów o określonej liczbie unikalnych znaków jest zliczona natychmiast. Ostateczna odpowiedź odpowiada następnie skumulowaną sumę wpisów z równą lub większą liczbą unikalnych znaków:

def DistinctChars (N, S):
    
    all_N = [0]*27
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_N[len(D)] += 1
    
    result = []
    s      =  0
    for i in range(26,0,-1):
        s += all_N[i]
        result.append(s)
    return reversed(result)
1
C-3PO 22 marzec 2021, 13:11