[imarid]

Da się znaleźć wszystkie możliwe substringi danego Stringa w czasie O(n)? Na rekrutacje miałem coś takiego i wała mi nie pasuje, żeby to można było zrobić w mniej jak O(n^2) ( ͡° ʖ̯ ͡°)
#programowanie

[leoha]

nieeeee, ma łapać ilość unikalnych znaków w ciągu

@imarid: no to liczba unikalnych znaków w "ACAX" to 3 (bo A, C, X), a w ACA to 2 (bo A, C), więc zastanów się co chcesz policzyć... no chyba, że chodzi, ile jest znaków, które występują dokładnie raz, ale to też jeszcze inne zadanie.
Szkoda, że nie masz oryginalnej treści, bo teraz to możemy tylko zgadywać

[imarid]

@leoha no unikalne w ciągu = występujące tylko raz, wysłałem ci kod z którego powinno to wynikać

[wolodia]

@imarid: Mozesz także wysłać mi kod?

[wolodia]

Liczysz dla każdego substringu unikalną ilość znaków.

@imarid: @leoha: Ty liczysz nie unikalną liczbę znaków ALE liczbę unikalnych znaków. Nie ile jest znaków bez powtórzeń, ale ile znaków występuje tylko raz. To zupełnie inny problem.

[wolodia]

@imarid: Skupiając się tylko na operacji na hashmap, zakładając że wszystko co robisz jest O(1), masz taką złożoność algorytmu:
\sigma{i=0}^{N} \sigma{j=i+1}^{N} j - i

Przecież to jest O(N^3).

[leoha]

Ty liczysz nie unikalną liczbę znaków ALE liczbę unikalnych znaków

@wolodia: tak, źe zrozumiałem OPa :)

[wolodia]

@imarid: @leoha: W tym algorytmie da się zejść bez problemu do O(N^2) - znajdujesz wygodną reprezentację substringa, przechowującą liczbę unikalnych znaków i jakiś hash określający unikalne znaki. W zewnętrznej pętli rozważasz wszystkie wyniki od substringi od 0 do i - (0, 1), (1, i-1), ..., (i-2,i-1) i dołączając do każdego nowy znak, tworząc przy okazji kolejny substring. Kluczem jest to, że omijasz trzecią petlę w ten sposób, że wykorzystujesz wyniki

[leoha]

@wolodia: zgadzam się
@imarid: poprawna treść zadania powinna brzmieć: "Znajdź sumę liczby unikalnych znaków wszystkich substringów" pytanie tylko czy tak brzmiało oryginalne zadania, bo jeśli tak to rzeczywiście poniżej O(n^2) narazie ciężko coś wymyślić.