Mam ciąg znaków, który składa się ze znaków A, B, C.i D i próbuję obliczyć długość najdłuższego podłańcucha, który ma równą ilość każdego z tych znaków w dowolnej kolejności. Na przykład ABCDB zwróci 4, ABCC 0 i ADDBCCBA 8.
Mój kod aktualnie:
public int longestSubstring(String word) {
HashMap<Integer, String> map = new HashMap<Integer, String>();
for (int i = 0; i<word.length()-3; i++) {
map.put(i, word.substring(i, i+4));
}
StringBuilder sb;
int longest = 0;
for (int i = 0; i<map.size(); i++) {
sb = new StringBuilder();
sb.append(map.get(i));
int a = 4;
while (i<map.size()-a) {
sb.append(map.get(i+a));
a+= 4;
}
String substring = sb.toString();
if (equalAmountOfCharacters(substring)) {
int length = substring.length();
if (length > longest)
longest = length;
}
}
return longest;
}
Obecnie działa to całkiem dobrze, jeśli długość łańcucha wynosi 10 ^ 4, ale staram się, aby to było 10 ^ 5. Wszelkie wskazówki i sugestie byłyby mile widziane.
Odpowiedzi:
0 dla odpowiedzi № 1Załóżmy, że
cnt(c, i)to liczba wystąpień postacicw prefiksie długościi.Podciąg
(low, high]ma równą liczbę dwóch znakówaibiffcnt(a, high) - cnt(a, low) = cnt(b, high) - cnt(b, low)lub, inaczej mówiąc,cnt(b, high) - cnt(a, high) = cnt(b, low) - cnt(a, low). Zatem każda pozycja jest opisana wartościącnt(b, i) - cnt(a, i). Teraz możemy uogólnić go na więcej niż dwa znaki: każda pozycja jest opisana przez krotkę(cnt(a_2, i) - cnt(a_1, i), ..., cnt(a_k, i) - cnt(a_1, i)), gdziea_1 ... a_kjest alfabet.Możemy iterować po podanym ciągu i zachować bieżącą krotkę. Na każdym kroku powinniśmy aktualizować odpowiedź, sprawdzając wartość
i - first_occurrence(current_tuple), gdziefirst_occurrenceto tablica skrótów, która przechowuje pierwsze wystąpienie każdej krotki do tej pory. Nie zapomnij wstawić krotki zer do mapy skrótu przed iteracją (odpowiada to pustemu prefiksowi).
0 dla odpowiedzi nr 2
Gdyby były tylko litery „A” i „B”, możesz zrobić coś takiego.
def longest_balanced(word):
length = 0
cumulative_difference = 0
first_index = {0: -1}
for index, letter in enumerate(word):
if letter == "A":
cumulative_difference += 1
elif letter == "B":
cumulative_difference -= 1
else:
raise ValueError(letter)
if cumulative_difference in first_index:
length = max(length, index - first_index[cumulative_difference])
else:
first_index[cumulative_difference] = index
return length
Życie jest bardziej skomplikowane ze wszystkimi czterema literami,ale pomysł jest taki sam. Zamiast utrzymywać tylko jedną różnicę skumulowaną, dla A w porównaniu do B, zachowujemy trzy, dla A w porównaniu do B, A w porównaniu do C i A w porównaniu do D.
0 dla odpowiedzi № 3
Po pierwsze, powstrzymaj się od budowania jakichkolwiek łańcuchów.
Jeśli nie produkujesz żadnych śmieci (lub prawie ich nie ma), nie ma potrzeby ich zbierania, co jest dużym plusem.
Następnie użyj innej struktury danych:
Proponuję 4-bajtowe tablice, przechowujące liczbę ich odpowiednich symboli w 4-przęsle, zaczynając od odpowiedniego indeksu łańcuchowego.
To powinno znacznie przyspieszyć.
0 dla odpowiedzi nr 4
Możesz policzyć występowanie postaci word. Wtedy możliwym rozwiązaniem może być:
- Gdyby
minto minimalna liczba wystąpień dowolnego znaku wword, następnieminjest również maksymalną możliwą liczbą wystąpień każdego znaku w szukanym podłańcuchu. W poniższym kodzieminjestmaxCount. - Iterujemy po malejących wartościach
maxCount. Na każdym kroku szukany ciąg będzie miał długośćmaxCount * alphabetSize. Możemy to postrzegać jako rozmiar przesuwanego okna, nad którym możemy się przesuwaćword. - Zasuwamy okno
word, zliczając wystąpienia znaków w oknie. Jeśli okno jest podciągiem, którego szukamy, zwracamy wynik. W przeciwnym razie kontynuujemy poszukiwania.
[NAPRAWIONY] Kod:
private static final int ALPHABET_SIZE = 4;
public int longestSubstring(String word) {
// count
int[] count = new int[ALPHABET_SIZE];
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
count[c - "A"]++;
}
int maxCount = word.length();
for (int i = 0; i < count.length; i++) {
int cnt = count[i];
if (cnt < maxCount) {
maxCount = cnt;
}
}
// iterate over maxCount until found
boolean found = false;
while (maxCount > 0 && !found) {
int substringLength = maxCount * ALPHABET_SIZE;
found = findSubstring(substringLength, word, maxCount);
if (!found) {
maxCount--;
}
}
return found ? maxCount * ALPHABET_SIZE : 0;
}
private boolean findSubstring(int length, String word, int maxCount) {
int startIndex = 0;
boolean found = false;
while (startIndex + length <= word.length()) {
int[] count = new int[ALPHABET_SIZE];
for (int i = startIndex; i < startIndex + length; i++) {
char c = word.charAt(i);
int cnt = ++count[c - "A"];
if (cnt > maxCount) {
break;
}
}
if (equalValues(count, maxCount)) {
found = true;
break;
} else {
startIndex++;
}
}
return found;
}
// Returns true if all values in c are equal to value
private boolean equalValues(int[] count, int value) {
boolean result = true;
for (int i : count) {
if (i != value) {
result = false;
break;
}
}
return result;
}
[POŁĄCZONE] Jest to rozwiązanie Hollisa Waite'a wykorzystujące zliczenia kumulacyjne, ale biorące pod uwagę moje obserwacje w punktach 1. i 2. Może to poprawić wydajność dla niektórych danych wejściowych:
private static final int ALPHABET_SIZE = 4;
public int longestSubstring(String word) {
// count
int[][] cumulativeCount = new int[ALPHABET_SIZE][];
for (int i = 0; i < ALPHABET_SIZE; i++) {
cumulativeCount[i] = new int[word.length() + 1];
}
int[] count = new int[ALPHABET_SIZE];
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
count[c - "A"]++;
for (int j = 0; j < ALPHABET_SIZE; j++) {
cumulativeCount[j][i + 1] = count[j];
}
}
int maxCount = word.length();
for (int i = 0; i < count.length; i++) {
int cnt = count[i];
if (cnt < maxCount) {
maxCount = cnt;
}
}
// iterate over maxCount until found
boolean found = false;
while (maxCount > 0 && !found) {
int substringLength = maxCount * ALPHABET_SIZE;
found = findSubstring(substringLength, word, maxCount, cumulativeCount);
if (!found) {
maxCount--;
}
}
return found ? maxCount * ALPHABET_SIZE : 0;
}
private boolean findSubstring(int length, String word, int maxCount, int[][] cumulativeCount) {
int startIndex = 0;
int endIndex = (startIndex + length) - 1;
boolean found = true;
while (endIndex < word.length()) {
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (cumulativeCount[i][endIndex] - cumulativeCount[i][startIndex] != maxCount) {
found = false;
break;
}
}
if (found) {
break;
} else {
startIndex++;
endIndex++;
}
}
return found;
}
0 dla odpowiedzi № 5
Prawdopodobnie będziesz chciał buforować łączną liczbę znaków dla każdego indeksu ciągu — to jest prawdziwe wąskie gardło. Nie zostały dokładnie przetestowane, ale coś takiego jak poniżej powinno działać.
public class Test {
static final int LEN = 4;
static class RandomCharSequence implements CharSequence {
private final Random mRandom = new Random();
private final int mAlphabetLen;
private final int mLen;
private final int mOffset;
RandomCharSequence(int pLen, int pOffset, int pAlphabetLen) {
mAlphabetLen = pAlphabetLen;
mLen = pLen;
mOffset = pOffset;
}
public int length() {return mLen;}
public char charAt(int pIdx) {
mRandom.setSeed(mOffset + pIdx);
return (char) (
"A" +
(mRandom.nextInt() % mAlphabetLen + mAlphabetLen) % mAlphabetLen
);
}
public CharSequence subSequence(int pStart, int pEnd) {
return new RandomCharSequence(pEnd - pStart, pStart, mAlphabetLen);
}
@Override public String toString() {
return (new StringBuilder(this)).toString();
}
}
public static void main(String[] pArgs) {
Stream.of("ABCDB", "ABCC", "ADDBCCBA", "DADDBCCBA").forEach(
pWord -> System.out.println(longestSubstring(pWord))
);
for (int i = 0; ; i++) {
final double len = Math.pow(10, i);
if (len >= Integer.MAX_VALUE) break;
System.out.println("Str len 10^" + i);
for (int alphabetLen = 1; alphabetLen <= LEN; alphabetLen++) {
final Instant start = Instant.now();
final int val = longestSubstring(
new RandomCharSequence((int) len, 0, alphabetLen)
);
System.out.println(
String.format(
" alphabet len %d; result %08d; time %s",
alphabetLen,
val,
formatMillis(ChronoUnit.MILLIS.between(start, Instant.now()))
)
);
}
}
}
static String formatMillis(long millis) {
return String.format(
"%d:%02d:%02d.%03d",
TimeUnit.MILLISECONDS.toHours(millis),
TimeUnit.MILLISECONDS.toMinutes(millis) -
TimeUnit.HOURS.toMinutes(TimeUnit.MILLISECONDS.toHours(millis)),
TimeUnit.MILLISECONDS.toSeconds(millis) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis)),
TimeUnit.MILLISECONDS.toMillis(millis) -
TimeUnit.SECONDS.toMillis(TimeUnit.MILLISECONDS.toSeconds(millis))
);
}
static int longestSubstring(CharSequence pWord) {
// create array that stores cumulative char counts at each index of string
// idx 0 = char (A-D); idx 1 = offset
final int[][] cumulativeCnts = new int[LEN][];
for (int i = 0; i < LEN; i++) {
cumulativeCnts[i] = new int[pWord.length() + 1];
}
final int[] cumulativeCnt = new int[LEN];
for (int i = 0; i < pWord.length(); i++) {
cumulativeCnt[pWord.charAt(i) - "A"]++;
for (int j = 0; j < LEN; j++) {
cumulativeCnts[j][i + 1] = cumulativeCnt[j];
}
}
final int maxResult = Arrays.stream(cumulativeCnt).min().orElse(0) * LEN;
if (maxResult == 0) return 0;
int result = 0;
for (int initialOffset = 0; initialOffset < LEN; initialOffset++) {
for (
int start = initialOffset;
start < pWord.length() - result;
start += LEN
) {
endLoop:
for (
int end = start + result + LEN;
end <= pWord.length() && end - start <= maxResult;
end += LEN
) {
final int substrLen = end - start;
final int expectedCharCnt = substrLen / LEN;
for (int i = 0; i < LEN; i++) {
if (
cumulativeCnts[i][end] - cumulativeCnts[i][start] !=
expectedCharCnt
) {
continue endLoop;
}
}
if (substrLen > result) result = substrLen;
}
}
}
return result;
}
}
0 dla odpowiedzi № 6
Załóżmy, że w ciągu o długości N jest K możliwych liter. Możemy śledzić równowagę liter widzianych za pomocą wektora poz o długości K, która jest aktualizowana w następujący sposób:
- Jeśli widzisz literę 1, dodaj (K-1, -1, -1, ...)
- Jeśli widzisz literę 2, dodaj (-1, K-1, -1, ...)
- Jeśli widzisz literę 3, dodaj (-1, -1, K-1, ...)
Utrzymuj hash, który mapuje pos na pierwszą pozycję ciągu, w której osiągnięto pos. Zrównoważone podciągi występują zawsze, gdy hash[pos] już istnieje, a wartość podciągu to s[hash[pos]:pos].
Koszt utrzymania hasha to O(log N) więcprzetwarzanie ciągu trwa O(N log N). Jak to wygląda w porównaniu z dotychczasowymi rozwiązaniami? Tego typu problemy mają zazwyczaj liniowe rozwiązania, ale jeszcze na jedno nie natknąłem się.
Oto kod demonstrujący pomysł na 3litery i bieg przy użyciu stronniczych ciągów losowych. (Jednolite losowe ciągi pozwalają na rozwiązania, które mają około połowy długości ciągu, co jest niewygodne do drukowania).
#!/usr/bin/python
import random
from time import time
alphabet = "abc"
DIM = len(alphabet)
def random_string(n):
# return a random string over choices[] of length n
# distribution of letters is non-uniform to make matches harder to find
choices = "aabbc"
s = ""
for i in range(n):
r = random.randint(0, len(choices) - 1)
s += choices[r]
return s
def validate(s):
# verify frequencies of each letter are the same
f = [0, 0, 0]
a2f = {alphabet[i] : i for i in range(DIM)}
for c in s:
f[a2f[c]] += 1
assert f[0] == f[1] and f[1] == f[2]
def longest_balanced(s):
"""return length of longest substring of s containing equal
populations of each letter in alphabet"""
slen = len(s)
p = [0 for i in range(DIM)]
vec = {alphabet[0] : [2, -1, -1],
alphabet[1] : [-1, 2, -1],
alphabet[2] : [-1, -1, 2]}
x = -1
best = -1
hist = {str([0, 0, 0]) : -1}
for c in s:
x += 1
p = [p[i] + vec[c][i] for i in range(DIM)]
pkey = str(p)
if pkey not in hist:
hist[pkey] = x
else:
span = x - hist[pkey]
assert span % DIM == 0
if span > best:
best = span
cand = s[hist[pkey] + 1: x + 1]
print("best so far %d = [%d,%d]: %s" % (best,
hist[pkey] + 1,
x + 1,
cand))
validate(cand)
return best if best > -1 else 0
def main():
#print longest_balanced( "aaabcabcbbcc" )
t0 = time()
s = random_string(1000000)
print "generate time:", time() - t0
t1 = time()
best = longest_balanced( s )
print "best:", best
print "elapsed:", time() - t1
main()
Przykładowe uruchomienie na wejściu 10^6 liter z alfabetem składającym się z 3 liter:
$ ./bal.py
...
best so far 189 = [847894,848083]: aacacbcbabbbcabaabbbaabbbaaaacbcaaaccccbcbcbababaabbccccbbabbacabbbbbcaacacccbbaacbabcbccaabaccabbbbbababbacbaaaacabcbabcbccbabbccaccaabbcabaabccccaacccccbaacaaaccbbcbcabcbcacaabccbacccacca
best: 189
elapsed: 1.43609690666