Parantezleri geçerli kılmak için en az silme

Problem

Küçük harfler ile ( ve ) karakterlerinden oluşan bir string veriliyor. Mümkün olan en az sayıda parantez silerek parantezleri dengeli bir string elde et ve onu döndür. Harfler silinmez ve kalan karakterlerin sırası değişmez. Birden fazla geçerli sonuç varsa herhangi biri kabul edilir.

Girdi:  "a)b(c)d"
Çıktı:  "ab(c)d"     (eşi olmayan ')' silindi)

Girdi:  "))(("
Çıktı:  ""           (hiçbir parantezin eşi yok)

Netleştirme soruları

• Sadece tek tür parantez mi? (Evet; üç tür olsaydı problem değişirdi.)
• Birden çok doğru cevap varsa herhangi biri mi? ("((x)" için "(x)" tek cevap; ama "(a)(b" gibi girdilerde hangi açılışın silineceği değişebilir.)
• Harfler yok sayılır mı, sadece parantezler mi önemli?
• Uzunluk? (10⁵; string birleştirmede O(n²)'ye düşmemek önemli.)

İpuçları

Yaklaşım

Brute force: Parantezlerin tüm alt kümelerini silmeyi dene, geçerli olanlar içinde en uzun kalanı seç. O(2ⁿ × n). Testlerde küçük girdiler için referans olarak bunu kullandım; mülakatta sadece söylenir.

Optimal, index stack'i: Silinmesi gereken parantezler iki türdür:

1. Eşi olmayan kapanışlar: soldan tararken, o ana kadar kapanmamış açılış yokken gelen ).
2. Eşi olmayan açılışlar: tarama bittiğinde hâlâ kapanmamış (.

Bu iki kümeyi silmek hem yeterlidir (kalan her ) bir ( ile eşleşmiş, kalan her ( bir ) ile kapanmıştır) hem de minimumdur: her silinen parantez gerçekten eşsizdir ve herhangi bir dengeli sonuç, eşleşen çiftlerin en fazla bu kadarını koruyabilir. Soldan sağa açgözlü eşleştirme mümkün olan en çok çifti eşleştirir.

Açılışların index'lerini stack'te tutmak, sonda hangi açılışların kaldığını bilmemizi sağlar. Silinecekleri boolean[] ile işaretleyip sonucu tek bir StringBuilder geçişinde kurarız.

Alternatif, iki geçiş, stack'siz: Soldan geçişte sayaçla eşsiz )'leri at; sağdan geçişte aynı şeyi ( için yap. O(n) zaman; stack yerine ikinci bir geçiş. İki versiyon da kabul edilir. Meta'da sık gelen bir takip, "O(1) ek bellekle (çıktı hariç) yapabilir misin?" sorusudur: ilk geçişte toplam açılış sayısından eşsiz kalanları hesaplayıp ikinci geçişte sondaki fazla açılışları atlamak yeterlidir.

String'i s = s.substring(0, i) + s.substring(i + 1) ile parça parça silmek her silmede O(n) kopya yapar ve O(n²)'ye çıkar; sık görülen bir performans hatası.

Java çözümü

import java.util.ArrayDeque;
import java.util.Deque;

public final class MinimumRemoveToMakeValid {

    public String minRemoveToMakeValid(String s) {
        boolean[] remove = new boolean[s.length()];
        Deque<Integer> openIndexes = new ArrayDeque<>();           // henüz eşleşmemiş '(' index'leri
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                openIndexes.push(i);
            } else if (c == ')') {
                if (openIndexes.isEmpty()) {
                    remove[i] = true;                              // eşi olmayan kapanış
                } else {
                    openIndexes.pop();
                }
            }
        }
        for (int index : openIndexes) {
            remove[index] = true;                                  // sonuna kadar kapanmamış açılışlar
        }
        StringBuilder result = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            if (!remove[i]) {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}

Karmaşıklık

• Zaman: O(n); bir tarama, stack'te kalanların işaretlenmesi ve bir kurma geçişi.
• Bellek: O(n); boolean[], stack ve sonuç. (Çıktı hariç O(1) ek bellek de mümkün; yukarıdaki alternatife bak.)

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. Birden fazla doğru cevap olabildiği için rastgele testte çıktının birebir eşitliği değil üç özelliği kontrol edildi: sonuç dengeli, sonuç girdinin bir alt dizisi ve uzunluğu, 2ⁿ alt kümeyi deneyen brute force'un bulduğu maksimum uzunluğa eşit. 3.000 rastgele girdi (()ab alfabesi, 0-11 uzunluk) kullanıldı.

Mülakatçı için

Meta'nın en sık sorduğu sorulardan biri. Ayrım noktaları: adayın neyin silinmesi gerektiğini iki ayrı küme olarak tanımlaması, string'i O(n²) kopyalama tuzağına düşmemesi ve neden minimum olduğunu kısaca gerekçelendirmesi. Hızlı biten adaya O(1) ek bellek takibi verilir.

İpucu zamanlaması: Aday yalnızca eşsiz kapanışları silip açılışları unutursa "((x)" örneğini ver. substring ile silme yaparsa kod bitince karmaşıklığını sor; O(n) sanıyorsa String immutability'sini hatırlat. Stack'te karakter tutup index tutmazsa sonda hangi açılışı sileceğini nasıl bileceğini sor.

Takip soruları:

1. Çıktı hariç O(1) ek bellekle yap. (Beklenen: ilk geçişte eşsiz kapanışları atlayıp toplam açılış ve eşleşme sayısını say; ikinci geçişte fazla açılışları sondan başlayarak at.)
2. Tüm olası minimum-silme sonuçlarını döndür. (Beklenen: BFS ya da backtracking; LeetCode 301, Remove Invalid Parentheses, Zor.)
3. Üç tür parantez olsaydı (()[]{}) açgözlü çözüm hâlâ minimum mu? (Beklenen: garanti edilmez; bir kapanış tepedeki açılışla uyuşmadığında kapanışı mı, açılışı mı sileceğin sonucu etkiler ve yerel karar her zaman doğru olmaz. Genel çözüm, en uzun dengeli alt dizi için aralık DP'si, O(n³).)

Benzer problemler

• Valid Parentheses (LeetCode 20) (bu sette: valid-parentheses).
• Minimum Add to Make Parentheses Valid (LeetCode 921).
• Remove Invalid Parentheses (LeetCode 301).
• Longest Valid Parentheses (LeetCode 32).