[NotABigFan]

Dzisiaj zadanie od Amazon:

Dana jest liczba k i napis s. Znajdź długość najdłuższego podłańcucha s, który składa się z najwyżej k różnych znaków.

np.:
dla s = "abcba", k = 2 wynikiem jest 3 (podłańcuch "bcb")

#dailycodingproblem #programowanie

[S.....s]

@NotABigFan: jest jakieś ograniczenie na złożoność? czy trzeba samemu kombinować? xd

[NotABigFan]

@SuppressWarnings: W zadaniu nie było. Ja to zrobiłem w czasie O(n) i pamięci O(k) ale może da się lepiej ( ͡° ͜ʖ ͡°)

[S.....s]

@NotABigFan: chyba bym zrobił, że mam tablicę z indeksami od 'a' do 'z' z licznikiem wystąpień
dodatkowo trzymam sobie aktualną ilość różnych znaków (zwiększana, jeśli w tablicy coś się zmienia z 0 na 1, zmienjszana jeśli na 0)
tworze 2 wskaźniki i lecę po tablicy i aktualizuję tablice, jeśli k mi przekroczy limit to zwiększam mniejszy licznik, jeśli nie to ten większy

[NotABigFan]

@SuppressWarnings: Właśnie luknąłem i zrobiłem jednak w pamięci O(n)

[S.....s]

@NotABigFan: tylko nie jestem pewien czy to zadziała dla każdych danych, czy te indeksy nie pominą jakiegoś przedziału, to byłoby by wtedy O(n), O(1)

[NotABigFan]

@SuppressWarnings: Faktycznie to może działać ale kod się liczy ( ͡° ͜ʖ ͡°)

[bladykiel]

@NotABigFan: Na szybko (byle działało) wyszło mi coś takiego :) Jak znajdę chwilkę czasu, to napiszę to lepiej :) (musi się dać to wykonać tylko z jednym forem)

private static String getMaxSubstring(String text, int k) {
char[] str = text.toCharArray();
String s = "";
Set set = new HashSet<>();
int from = 0;
int count = 0;
int finalSize = 0;
for (int i = 0; i < str.length; i++) {

[NotABigFan]

@bladykiel: jeżeli to dobrze rozumiem to działa w O(n^2) czyli jest miejsce do poprawy jakby co( ͡° ͜ʖ ͡°)

[bladykiel]

@NotABigFan: Powinno być trochę lepiej :)

private static String getMaxSubstring2(String text, int k) {
char[] str = text.toCharArray();
String s = "";
int from = 0;
int counter = k+1;
Set set = new HashSet<>();

for (int i = 0; i < str.length; i++) {
if(i+counter>str.length){
break;
}
String[] c = text.substring(i, i + counter).split("");
set.addAll(Arrays.asList(c));
if (set.size() <= k) {
from = i;
counter += 1;
i=i-1;
}
set.clear();
}

[Frogof]

@NotABigFan: nie mam czasu pisać ale da się liniowo z pamięcią od k

[D.....n]

@NotABigFan: "podłańcuch" to substring czy subsequence?

[NotABigFan]

@Demolicjon: substring

[D.....n]

@NotABigFan: Nvm, właśnie zobaczyłem, że @SuppressWarnings podał już odpowiedź.

[Frogof]

@Demolicjon: jakby @SuppressWarnings zrobil zamiast tablicy slownik to by mial optymalnie.

[S.....s]

@Frogof ee co? xd niby w czym słownik lepszy?

[Frogof]

@SuppressWarnings: serio?:D nigdzie nie jest napisane ze znaki to a..z. Wiec alokowanie tablicy to kolejne O od wielkości alfabetu.

[S.....s]

@Frogof no ale zwykle w takich zadaniach jest a - z xd a przy słowniku też masz taką samą złożoność, ewentualnie ograniczoną przez n
Ale no dobra, w pewnych przypadkach słownik może zajmować mniej pamięci

[D.....n]

@Frogof: @SuppressWarnings: No przecież tablica to nic innego, jak słownik z "idealnym" kluczem. (⌐ ͡■ ͜ʖ ͡■)

Przy tak ograniczonym alfabecie jak a..z (a nawet niech będzie 0..255) tablica jest jedynie słusznym wyborem. Znany z góry rozmiar, błyskawiczna alokacja na stosie, zero narzutu. W słowniku będziesz zwykle miał alokację node-based, zwłaszcza w takich śmiechawych gunwojęzykach jak python. Skończy się na tym, że po ~10-12

[Frogof]

@Demolicjon: @SuppressWarnings: no to teraz taka tablice dla unicoda zaalokuj:) przy ograniczonym tak, ale tu nie jest ograniczony. Szczególnie w kontekście o jakim pisze @NotABigFan (rozmowy w dużych, dobrych firmach) zrobienie takiego upraszczajacego założenia to błąd.

[D.....n]

@Frogof: Mylisz się i dorabiasz ideologię. W takich zadankach są bardzo często stosowane uproszczenia, gdzie moje wspomnienie o zakresie bajtowym w bardzo wielu miejscach już jest przesadnie ostrożne. Co najwyżej jako follow-up mogłoby się pojawić o kodowanie znaków i ew. zmianę struktury danych.

Jak życie daje Ci cytry^Wograniczenia wejścia, to wykorzystaj je do ostatka.