Anagramları grupla

Problem

Küçük harflerden oluşan kelimelerden bir liste veriliyor. Aynı harfleri aynı sayıda içeren kelimeler (yani birbirinin harflerini yeniden dizerek elde edilebilenler) aynı gruba girmeli. Grupları liste olarak döndür; grupların ve grup içindeki kelimelerin sırası önemli değil. Aynı kelime listede iki kez geçerse ikisi de sonuçta yer alır.

Girdi:  ["kalem", "melak", "elma", "kelam", "alem", "su"]
Çıktı:  [["kalem", "melak", "kelam"], ["elma", "alem"], ["su"]]

Girdi:  ["", ""]
Çıktı:  [["", ""]]

Netleştirme soruları

• Alfabe ne? Sadece a-z mi, yoksa büyük harf, Türkçe karakter, Unicode var mı? (Sayaç dizisi boyutunu belirler.)
• Büyük-küçük harf duyarlı mı? "Elma" ile "alem" anagram mı?
• Boş string geçerli bir kelime mi?
• Çıktı sırası önemli mi? (Test deterministik olsun diye LinkedHashMap gerekebilir.)
• Kelime sayısı ve uzunluğu ne kadar? (n ≤ 10⁴, L ≤ 100 gibi; imza seçimini etkiler.)

İpuçları

Yaklaşım

Brute force: Her kelimeyi mevcut grupların temsilcileriyle karşılaştır; anagram kontrolü sayaçla O(L). Grup sayısı g ise O(n × g × L), en kötü durumda (hiçbiri anagram değil) O(n² × L).

Kanonik anahtar (imza) ile gruplama: Anagram olmak bir denklik ilişkisidir; her denklik sınıfına tek bir temsilci anahtar üretirsen gruplama Map<anahtar, List<kelime>> ile tek geçişte biter. İki imza seçeneği var:

1. Sıralanmış harfler: "melak" -> "aeklm". Basit ve her alfabede çalışır. Kelime başına O(L log L).
2. Harf sayaçları: 26 elemanlı dizi, "1#0#0#...#" gibi bir string'e çevrilir. Kelime başına O(L + 26). Uzun kelimelerde daha hızlı; alfabe sabit olmalı.

Sayaç anahtarında ayraç şarttır: ayraçsız birleştirmede 'b' harfinden 11, 'c' harfinden 1 olan kelimenin sayaç dizisi ...0,11,1,0... ile 'b'den 1, 'c'den 11 olanınki ...0,1,11,0... aynı "...0111 0..." string'ini üretir ve farklı kelimeler aynı gruba düşer. Testlerde bu durum ayrıca denendi.

computeIfAbsent ile "grup yoksa oluştur, sonra ekle" tek satıra iner; get + null kontrolü + put üçlüsüne gerek kalmaz.

Java çözümü

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

public final class GroupAnagrams {

    public List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String word : words) {
            groups.computeIfAbsent(signature(word), key -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }

    // "eat" -> "1#0#0#0#1#...": harf sayaçlarından kanonik anahtar, O(L)
    private static String signature(String word) {
        int[] counts = new int[26];
        for (int i = 0; i < word.length(); i++) {
            counts[word.charAt(i) - 'a']++;
        }
        StringBuilder key = new StringBuilder(26 * 2);
        for (int count : counts) {
            key.append(count).append('#');                         // ayraç: "1,11" ile "11,1" karışmasın
        }
        return key.toString();
    }
}

Karmaşıklık

• Zaman: O(n × L). Her kelime için sayaç O(L), anahtar üretimi O(26), map işlemleri anahtar uzunluğu kadar (hash ve equals) O(26). Sıralama imzasıyla O(n × L log L) olurdu.
• Bellek: O(n × L): tüm kelimeler gruplarda tutulur, artı grup başına bir anahtar.
• L küçükse (ör. ≤ 10) iki yaklaşım arasındaki fark pratikte önemsizdir; mülakatta sıralama imzasıyla başlayıp sayaç optimizasyonunu söylemek yeterli.

Kenar durumlar ve testler

Çözüm main içindeki testlerle derlenip çalıştırıldı; grupların sırası önemsiz olduğu için karşılaştırma, grupları sıralayıp kümeye çevirerek yapıldı. Ek olarak 1.000 rastgele girdide (3 harfli alfabeden 0-3 uzunlukta kelimeler) sıralama imzalı referans çözümle aynı grupları verdiği doğrulandı.

Dikkat: alfabe varsayımı kodda word.charAt(i) - 'a' satırında gizli. Büyük harf ya da ş gelirse ArrayIndexOutOfBoundsException alırsın. Mülakatta bu varsayımı yüksek sesle söylemek ve genel alfabe için sıralama imzasına ya da Map<Character, Integer> sayacına geçileceğini belirtmek beklenir.

Mülakatçı için

Bu soruda gözlemlenecek asıl beceri "eşdeğer olanları grupla" kalıbını tanıyıp kanonik anahtar üretmek. Çoğu aday sıralama imzasını hızlıca bulur; ayrım, sayaç imzasına geçerken ayraç problemini görüp görmediği ve alfabe varsayımını sorup sormadığıdır.

İpucu zamanlaması: Aday ikili karşılaştırma yapan O(n²) bir çözümde takılırsa "anagramlar için ortak bir temsil olabilir mi?" diye sor. Sayaç anahtarını ayraçsız yazarsa doğrudan söyleme; 11-1 ve 1-11 örneğini verip sonucu tahmin etmesini iste.

Takip soruları:

1. Anahtar olarak int[] kullansaydın ne olurdu? (Beklenen: referans eşitliği, her kelime ayrı grup; Arrays.hashCode'u saran bir record ya da List<Integer> kullanılabilir.)
2. Milyarlarca kelime var ve dağıtık işliyorsun. (Beklenen: map-reduce; map aşamasında imza anahtar olur, aynı anahtar aynı reducer'a gider. Spark'ta groupByKey.)
3. Unicode desteği gerekseydi? (Beklenen: code point'lerle çalışma, Map<Integer, Integer> sayaç ya da sıralanmış code point dizisi; normalizasyon (NFC) konusu.)

Benzer problemler

• Valid Anagram (LeetCode 242): iki kelimenin anagram olup olmadığı.
• Find All Anagrams in a String (LeetCode 438): sabit boyutlu kayan pencere + sayaç.
• Group Shifted Strings (LeetCode 249): farklı bir kanonik anahtar (harf farkları).
• Top K Frequent Elements (LeetCode 347): sayma ve gruplama (bu sette: top-k-frequent-elements).