Stringek és karaktergyakoriság

A stringes interjúfeladatok felszínen nagyon különbözőnek tűnnek, de sok közülük ugyanarra a néhány ötletre redukálható: normalizálás, számlálás, a megfelelő karakterállapot megőrzése, és annak eldöntése, hogy tömb vagy HashMap a jobb gyakorisági struktúra.

1. Definíció

Miről szól ez a téma?

Ez a téma arról szól, hogyan oldasz meg stringes feladatokat úgy, hogy explicit módon modellezed a karaktereket.

Ahelyett, hogy csak teljes szavakban gondolkodnál, sokszor inkább ezt nézed:

• karaktergyakoriság,
• első vagy utolsó előfordulási pozíció,
• normalizált reprezentáció,
• és hogy számít-e a sorrend vagy csak a multihalmaz tartalom.

Miért létezik?

Mert sok beginner és intermediate interjúkérdés valójában elrejtett számlálási feladat.

A prompt beszélhet:

• anagramokról,
• duplikátumokról,
• érvényes karakterekről,
• palindromokról,
• első egyedi karakterről,
• vagy csoportosított szavakról,

miközben a valódi bottleneck sokszor a frequency tracking.

Hová illeszkedik?

Ez a téma közvetlenül a tömbalapok után jön.

Ez természetes, mert a stringes feladatok gyakran végül ilyenekké válnak:

• karakter-számláló tömbös feladat,
• HashMap lookup feladat,
• vagy kétpasszos scan feladat.

Mi NEM ez a téma?

Ez nem az advanced string matchingről szól, mint a KMP vagy a Rabin-Karp.

Ez a korábbi interjús rétegről szól:

• számlálás,
• normalizálás,
• csoportosítás,
• és scanelés.

Miért szeretik ezt az interjúztatók?

A string feladatok jók arra, hogy lásd, tudsz-e:

• pontosan contractot olvasni,
• észrevenni a rejtett feltételezéseket,
• kompakt state modellt választani,
• és elkerülni a túltervezést.

Sok rossz stringes megoldás ott hibázik, hogy a jelölt nem tisztázta, mit kell ignorálni, normalizálni vagy számolni.

2. Alapfogalmak

String mint sorozatprobléma

Sok stringes feladat valójában karakterekkel dolgozó sorozatprobléma.

Ezért a hasznos kérdések gyakran ezek:

• mi a munkaegység,
• milyen state-nek kell fennmaradnia,
• és számít-e a sorrend?

Gyakoriságszámlálás

A gyakoriságszámlálás azt nézi, egy karakter hányszor jelenik meg.

Ez hasznos például:

• anagram ellenőrzésnél,
• duplikátum detektálásnál,
• majority-szerű gondolkodásnál,
• és kanonikus reprezentáció építésénél.

Tömb versus `HashMap`

Ha az ábécé kicsi és fix, akkor egy tömb sokszor a legtisztább választás.

Példák:

• kis angol betűk,
• nagybetűk,
• számjegyek,
• vagy ASCII-közeli promptok.

Ha a karaktertartomány nagyobb vagy bizonytalan, a HashMap<Character, Integer> biztonságosabb lehet.

Normalizálás

A normalizálás azt jelenti, hogy különbözőnek látszó inputokat közös, összehasonlítható formára alakítasz.

Tipikus lépések:

• lowercasing,
• szóközök kihagyása,
• írásjelek kihagyása,
• trimming,
• vagy sorted / counted signature készítése.

Kétpasszos scan

A two-pass scan gyakori stringes feladatokban.

Első passz:

• számlálást építesz,
• pozíciót tárolsz,
• vagy szerkezetet gyűjtesz.

Második passz:

• megkeresed az első jó választ,
• összehasonlítod a countokat,
• vagy grouped outputot építesz.

Kanonikus reprezentáció

A kanonikus reprezentáció egy stabil forma, amely lehetővé teszi, hogy a logikailag azonos stringek ugyanúgy hasonlítsanak.

Példák:

• rendezett karakterek anagramokhoz,
• count-signature mint a2#b1#c0...,
• normalizált lowercase alfanumerikus forma.

Sorrendérzékeny versus sorrendfüggetlen feladat

Ezt korán el kell dönteni.

Ha a sorrend számít, akkor a frequency-only megoldás kevés lehet.

Ha a sorrend nem számít, az eredeti elrendezés megőrzése felesleges munka lehet.

Karaktertartomány-feltételezések

Mindig kérdezd meg, milyen karakterek jelenhetnek meg.

Ez dönti el, hogy:

• elég-e az int[26],
• elég-e az int[128],
• vagy map-alapú megoldás kell.

Stringek Java-ban

Java-ban a String immutable.

Ez azt jelenti, hogy a cikluson belüli ismételt összefűzés drága lehet.

Tiszta számlálási feladatoknál általában kerülöd a fölösleges intermediate stringek építését.

Felismerési jelek

Ez a téma kapcsoljon be, ha a prompt olyan szavakat használ, mint:

• anagram,
• ismétlődő karakter,
• uniqueness,
• normalizált egyenlőség,
• vagy azonos betűtartalom szerinti csoportosítás.

3. Gyakorlati használat

Mikor jó első lépés a számlálás?

Akkor, ha a prompt azt kérdezi, hogy két string ugyanazokat a karaktereket tartalmazza-e, hogy egy karakter pontosan egyszer szerepel-e, vagy hogy több szó azonos betűösszetételű-e.

Mikor kell először normalizálni?

Akkor, ha a nagybetű-kisbetű különbség, az írásjelek vagy a whitespace nem számíthatnak a válaszban.

Mikor jobb a tömb, mint a map?

A tömböt válaszd, ha:

• fix az ábécé,
• a prompt garantálja a lowercase English letters inputot,
• vagy szorosabb memória- és konstans faktor kell.

Mikor jobb a map, mint a tömb?

A mapet válaszd, ha:

• nem fix a karaktertartomány,
• Unicode vagy vegyes szimbólumok is jöhetnek,
• vagy a prompt nem indokol kis domain feltételezést.

Tipikus interjús flow

Egy tiszta magyarázat gyakran így hangzik:

1. „Itt csak a karaktergyakoriság számít, az eredeti sorrend nem.”
2. „A prompt garantálja a lowercase English letters bemenetet.”
3. „Ezért elég egy int[26].”
4. „Egy passzban frissítem a countokat.”
5. „Utána vagy összehasonlítom, vagy második passzban megkeresem a választ.”

Gyakori optimalizációs út

Gyakori út:

• naiv nested comparison,
• majd sorting,
• majd direkt counting.

A sorting sokszor elfogadható, de kis domain mellett a counting gyakran egyszerűbb és gyorsabb.

Pair-programming nyelv

Hasznos mondatok:

• „Ez valójában frequency probléma.”
• „Itt a sorrend irreleváns, ezért canonical form kell.”
• „Fix az alphabet, ezért a tömb jobb, mint a map.”
• „Compare előtt normalizálok.”
• „Ez két passzt igényel: először count, utána answer.”

4. Kódpéldák

Alap példa — valid anagram `int[26]`-tal

Ez a verzió lowercase English letters bemenetet feltételez.

public class ValidAnagramArray {
    public static boolean isAnagram(String left, String right) {
        if (left == null || right == null || left.length() != right.length()) {
            return false;
        }

        int[] counts = new int[26];

        for (int index = 0; index < left.length(); index++) {
            counts[left.charAt(index) - 'a']++;
            counts[right.charAt(index) - 'a']--;
        }

        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

Miért működik:

• azonos stringeknél a különbségcountok nullára futnak ki,
• kicsi a state,
• és lineáris az idő.

Alap példa — első egyedi karakter két passzal

public class FirstUniqueCharacter {
    public static int firstUniqueIndex(String text) {
        if (text == null || text.isEmpty()) {
            return -1;
        }

        int[] counts = new int[26];

        for (int index = 0; index < text.length(); index++) {
            counts[text.charAt(index) - 'a']++;
        }

        for (int index = 0; index < text.length(); index++) {
            if (counts[text.charAt(index) - 'a'] == 1) {
                return index;
            }
        }

        return -1;
    }
}

Ez klasszikus two-pass scan:

• először számolsz,
• utána megkeresed az első jó pozíciót.

Haladó példa — anagram csoportosítás canonical signature-rel

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public static List<List<String>> group(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            String signature = buildSignature(word);
            groups.computeIfAbsent(signature, ignored -> new ArrayList<>()).add(word);
        }

        return new ArrayList<>(groups.values());
    }

    private static String buildSignature(String word) {
        int[] counts = new int[26];

        for (int index = 0; index < word.length(); index++) {
            counts[word.charAt(index) - 'a']++;
        }

        StringBuilder builder = new StringBuilder();
        for (int count : counts) {
            builder.append('#').append(count);
        }

        return builder.toString();
    }
}

A kulcslépés egy olyan kanonikus reprezentáció építése, amely ignorálja a sorrendet, de megőrzi az összetételt.

Haladó példa — palindrome ellenőrzés normalizálással

public class NormalizedPalindrome {
    public static boolean isPalindrome(String text) {
        if (text == null) {
            return false;
        }

        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            char leftChar = Character.toLowerCase(text.charAt(left));
            char rightChar = Character.toLowerCase(text.charAt(right));

            if (!Character.isLetterOrDigit(leftChar)) {
                left++;
                continue;
            }

            if (!Character.isLetterOrDigit(rightChar)) {
                right--;
                continue;
            }

            if (leftChar != rightChar) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

Ez jó emlékeztető arra, hogy nem minden stringes feladat frequency task először.

Néha a normalizálás és a pointermozgás a valódi modell.

Gyakori hiba — rossz domain feltételezés

public class BrokenFrequencyCheck {
    public static boolean containsDuplicateLetter(String text) {
        int[] counts = new int[26];

        for (int index = 0; index < text.length(); index++) {
            counts[text.charAt(index) - 'a']++;
        }

        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }

        return false;
    }
}

Ez elromlik, ha az input tartalmazhat nagybetűt, számjegyet, írásjelet vagy nem angol karaktert.

A valódi bug nem szintaxis.

Hanem egy ki nem mondott domain feltételezés.

5. Trade-offok

Szempont	Részletek
⚡ Performance	A frequency arrayek és a two-pass scannek általában lineárisak, és nagyon jók a konstans faktoraik, ha fix az ábécé.
💾 Memory	A tömb kompakt, a map rugalmasabb, de nehezebb.
🔧 Maintainability	A counting megoldások rövidek és review-barátok, de csak akkor, ha a domain-feltételezések explicitek.
🔄 Flexibility	A map-alapú megoldások jobban kezelik a nagyobb karakterkészletet; a tömb szűkebb, de feszesebb megoldás.

Performance trade-off: A sorting sokszor jó elég, de kis domainnél a counting általában jobb.

Memory trade-off: Egy int[26] nagyon olcsó; a map rugalmasságot vesz nagyobb overheaddel.

Maintainability trade-off: A legtisztább kód sokszor az, amelyiknek a feltételezései ki vannak mondva.

Flexibility trade-off: Minél változatosabb az input, annál kevésbé biztonságos a hard-coded tömbdomain.

6. Gyakori hibák

1. Lowercase letters feltételezése bizonyíték nélkül
   Ez az egyik leggyakoribb csendes bug.

2. Normalizálási szabályok kihagyása
   A case, a whitespace és az írásjelek sokszor megváltoztatják a helyes modellt.

3. Sorting használata, amikor a counting egyszerűbb
   A sorting valid, de lehet fölösleges munka.

4. Counting használata, amikor a sorrend még mindig számít
   A frequency önmagában nem őriz sorrendinformációt.

5. Sok ideiglenes string építése feleslegesen
   Java-ban a loopon belüli string-összefűzés drágább lehet, mint kellene.

6. A two-pass szerkezet eltévesztése
   Néhány feladatnál előbb count kell, utána külön döntési passz.

7. A karakterdomain ki nem mondása
   A 26, 52, 128 és a HashMap különböző tervezési döntések, nem felcserélhető varázsszámok.

7. Mélyebb összefüggések

Miért redukálódnak jól a stringes feladatok?

A string promptok gyakran azért érződnek maszatosnak, mert a természetes nyelv maszatos.

De sokuk jól redukálható, ha megkérdezed, hogy a feladat valójában:

• normalizálás utáni egyenlőségről,
• multihalmaz-egyenlőségről,
• ritka karakter pozíciójáról,
• vagy csoportosítható tartalomról szól-e.

Miért ilyen népszerűek a counting arrayek?

Azért, mert a szükséges state-et egy kicsi, fix struktúrába sűrítik.

Ez ad:

• kiszámítható memóriát,
• kiszámítható hozzáférést,
• és egyszerű review-logikát.

A kanonikus forma ereje

A kanonikus formák lehetővé teszik, hogy másképp kinéző, de a prompt szabályai szerint azonos inputok ugyanúgy hasonlítsanak.

Ezért tér vissza újra és újra a sorted string, a count signature és a normalized lowercase forma.

A string nem mindig „csak string”

Néha a valódi modell inkább:

• tömbscan,
• hashing,
• two pointers,
• vagy window maintenance.

A string csak a tároló.

Java-specifikus óvatosság

Mivel a String immutable, a nagy mennyiségű rekonstrukciót loopban óvatosan kezeld.

Ha csak count, index vagy normalizált összehasonlítás kell, ne allokálj többet a szükségesnél.

A magyarázási előny

Egy erős magyarázat itt egyszerű:

• milyen input-feltételezés van,
• milyen state-et őrzöl meg,
• miért tömb vagy map a jó domain-struktúra,
• és számít-e a sorrend.

Ez már önmagában sokkal erősebb, mint az, hogy „csak használtam egy mapet”.

8. Interjúkérdések

Q: Mikor jobb az int[26], mint a HashMap<Character, Integer>?
A: Akkor, ha a prompt garantálja a lowercase English letters vagy más kicsi fix alphabet használatát.

Q: Miért használnak sok stringes feladatban két passzt?
A: Mert az első passz countot vagy szerkezetet épít, a második pedig ebből előállítja a szükséges választ.

Q: Mi a kanonikus reprezentáció?
A: Olyan stabil forma, amely logikailag azonos inputokat ugyanúgy hasonlít össze, például rendezett string vagy count signature.

Q: Mi a leggyakoribb csendes bug a character-frequency feladatokban?
A: Az, hogy a megoldás kisebb karakterdomaint feltételez, mint amit a prompt valójában garantál.

Q: Miért ilyen fontos a normalizálás?
A: Mert a case, a punctuation és a whitespace szabályai gyakran megváltoztatják, mit jelent az, hogy két string „egyenlő”.

9. Fogalomtár

Fogalom	Definíció
frequency counting	Annak követése, hogy egy karakter hányszor jelenik meg.
normalization	Az input közös, összehasonlítható formára hozása.
canonical representation	Stabil reprezentáció összehasonlításhoz vagy csoportosításhoz.
two-pass scan	Egy passz state-gyűjtésre, egy másik a válaszadásra.
character domain	Az a karakterkészlet, amelyet az input tartalmazhat.
immutable	Olyan érték, amely létrehozás után nem módosítható in-place.
signature	A string logikai tartalmát sűrítő reprezentáció.

10. Cheatsheet

• Kérdezd meg, számít-e a sorrend.
• Kérdezd meg, milyen karakterdomain garantált.
• Ha a prompt kéri, compare előtt normalizálj.
• Fix lowercase-letter feladatokra jó az int[26].
• Bizonytalan vagy széles domainre jobb a map.
• A two-pass scan gyakori és sokszor a legtisztább.
• A sorting valid, de a counting olcsóbb lehet.
• A frequency önmagában nem őriz sorrendérzékeny jelentést.
• Interjún mondd ki a feltételezéseidet.
• Sok stringes feladat valójában elrejtett counting probléma.