En fazla bir silmeyle palindrom

Problem

Bir string veriliyor. Bu string'den en fazla bir karakter silerek (ya da hiç silmeden) soldan ve sağdan aynı okunan bir string (palindrom) elde edebilir misin? true ya da false döndür.

Girdi:  "kayvak"
Çıktı:  true       ('v' silinirse "kayak")

Girdi:  "kayvakz"
Çıktı:  false      (en az iki silme gerekir)

Netleştirme soruları

• Sadece küçük harf mi, yoksa boşluk/noktalama da var mı? Onlar yok sayılmalı mı? (LeetCode 125'ten farklı olarak bu versiyonda her karakter sayılır.)
• Büyük-küçük harf duyarlı mı?
• Zaten palindromsa true mu? (Evet, "en fazla bir" silme.)
• Boş string ve tek karakter? (İkisi de palindrom.)
• Uzunluk ne kadar? (10⁵; O(n²) çözüm sınırda kalır.)

İpuçları

Yaklaşım

Brute force: Her index'i sırayla silip kalan string'in palindrom olup olmadığını kontrol et (artı hiç silmeme durumu). n silme × O(n) kontrol = O(n²). n = 10⁵ için 10¹⁰ işlem; çok yavaş.

Optimal, iki işaretçi + tek dallanma: İki uçtan içeri yürü. Karakterler eşit olduğu sürece ilerle; bu karakterler zaten eşleşiyor ve hiçbir silme onları bozmaz. İlk uyuşmazlıkta (s[left] != s[right]) palindrom elde etmenin tek yolu bu iki karakterden birini silmek: başka bir yeri silmek bu iki karakterin karşı karşıya gelmesini değiştirmez. Böylece iki aday kalır: s[left+1..right] ya da s[left..right-1]. İkisinden biri palindromsa cevap true.

Neden açgözlü yaklaşım güvenli? Dış kısımdaki eşleşen karakterleri "harcamadan" geçtik; silme hakkını ilk uyuşmazlıkta kullanmak zorundayız çünkü ondan önce bir şey silmek dış eşleşmeleri kaydırır ve uyuşmazlığı ortadan kaldırmaz. Kritik nokta, iki dalın da denenmesi: sadece soldakini silmeyi deneyen kod "cbbcc" gibi bir girdide yanlış cevap verir (burada sağdaki c silinmeli).

Java çözümü

public final class ValidPalindromeII {

    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // Tek silme hakkı: ya soldakini ya sağdakini at, kalan kısım palindrom olmalı
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }

    private static boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

isPalindrome alt aralıkla çalışıyor; substring ile yeni string üretmek her dalda O(n) ek bellek harcardı. Aralık parametreleri bunu O(1)'de tutar.

Karmaşıklık

• Zaman: O(n). Ana döngü en fazla n/2 adım; uyuşmazlıktan sonra iki isPalindrome çağrısı, her biri kalan aralık kadar. Dallanma yalnızca bir kez olduğu için toplam en fazla ~2n karşılaştırma.
• Bellek: O(1).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 5.000 rastgele string'de (3 harfli alfabe, 0-9 uzunluk) "her index'i silip dene" brute force'u ile karşılaştırıldı. Küçük alfabe, tekrar eden karakterler sayesinde zor dallanma durumlarını sık üretir.

Mülakatçı için

Meta'nın telefon mülakatlarında sık geçen bu soru, kolay görünmesine rağmen iki tuzak içerir: sadece bir dalı denemek ve silme hakkını yanlış takip etmek (bir sayaçla "bir kez sildim" diye işaretleyip ana döngüye devam etmek, hangi tarafı silmen gerektiğini bilmediğin için hatalıdır). Asıl sinyal, adayın neden yalnızca iki dalın yeterli olduğunu açıklayabilmesi.

İpucu zamanlaması: Aday brute force'ta kalırsa "ilk uyuşmazlığa kadar olan kısım hakkında ne biliyorsun?" diye sor. Tek dal yazarsa "cbbcc" girdisini ver ve kodla birlikte yürütmesini iste. Rekürsif bir "silme hakkı" parametresiyle genel çözüm yazmaya çalışıyorsa (k silme), bunun bu soru için gereksiz olduğunu ama takip sorusunda işe yarayacağını söyleyebilirsin.

Takip soruları:

1. En fazla k silme hakkı olsaydı? (Beklenen: naif dallanma O(2^k × n); doğru çözüm "en uzun palindromik alt dizi" DP'si ile n - LPS <= k kontrolü, O(n²); LeetCode 1216.)
2. Hangi karakterin silineceğini de döndürmen gerekseydi? (Beklenen: başarılı dalın index'i; silme yoksa -1.)
3. Alfanümerik olmayan karakterler yok sayılsın ve harf duyarsız olsun dersem? (Beklenen: işaretçileri ilerletirken Character.isLetterOrDigit ile atlama, Character.toLowerCase ile karşılaştırma.)

Benzer problemler

• Valid Palindrome (LeetCode 125): temel iki işaretçi kontrolü.
• Valid Palindrome III (LeetCode 1216): k silme, DP.
• Longest Palindromic Substring (LeetCode 5): merkezden genişleme.
• Container With Most Water (LeetCode 11): iki uçtan içeri yürüyen işaretçiler (bu sette: container-with-most-water).