En Uzun Tekrarlanmayan Karakter Alt Dizisi: JavaScript Çözümü

En Uzun Tekrarlanmayan Karakter Alt Dizisi: JavaScript Çözümü

Merhaba! Fatih Soysal burada. Bu yazıda, LeetCode’un oldukça popüler problemlerinden biri olan “En Uzun Tekrarlanmayan Karakter Alt Dizisi” problemini ele alacağız. JavaScript kullanarak bu problemi nasıl çözebileceğimize dair adım adım bir rehber sunacağım. Öncelikle sorunu daha iyi anlamak için problemi tanımlayalım. Problem, verilen bir string içinde tekrar eden karakter içermeyen en uzun alt dizinin uzunluğunu bulmayı hedefliyor. Örneğin, “abcabcbb” stringi için cevap “abc” olup uzunluğu 3’tür. Bu yazıda, hem problemi anlamak hem de etkili bir JavaScript çözümü geliştirmek için birlikte çalışacağız.

Problemin çözümünde, kayan pencere tekniğini kullanacağız. Bu teknik, string üzerinde bir pencereyi kaydırarak, pencere içinde tekrar eden karakter olup olmadığını kontrol etmeyi sağlar. Eğer tekrar eden bir karakter bulursak, pencerenin başlangıcını kaydırarak tekrar eden karakteri pencerenin dışına taşıyoruz. Bu işlemi, stringin sonuna ulaşana kadar tekrarlıyoruz. Her adımda, pencerenin uzunluğunu takip ederek en uzun tekrarlanmayan alt dizinin uzunluğunu buluyoruz. Şimdi, JavaScript koduna geçelim.

İşte kayan pencere tekniğini kullanan JavaScript çözümü:

function longestSubstringWithoutRepeatingCharacters(s) {
  let longestSubstringLength = 0;
  let startIndex = 0;
  let charIndexMap = {}; // Karakterlerin indekslerini tutmak için bir map kullanıyoruz

  for (let endIndex = 0; endIndex < s.length; endIndex++) {
    const char = s[endIndex];

    // Eğer karakter daha önce pencerede varsa
    if (charIndexMap[char] !== undefined && charIndexMap[char] >= startIndex) {
      // Pencerenin başlangıç indeksini güncelliyoruz
      startIndex = charIndexMap[char] + 1;
    }

    // Karakterin indeksini güncelliyoruz
    charIndexMap[char] = endIndex;

    // En uzun alt dizinin uzunluğunu güncelliyoruz
    longestSubstringLength = Math.max(longestSubstringLength, endIndex - startIndex + 1);
  }

  return longestSubstringLength;
}

// Örnek kullanım:
console.log(longestSubstringWithoutRepeatingCharacters("abcabcbb")); // Çıktı: 3
console.log(longestSubstringWithoutRepeatingCharacters("bbbbb")); // Çıktı: 1
console.log(longestSubstringWithoutRepeatingCharacters("pwwkew")); // Çıktı: 3

Bu kod, her karakter için indeksini tutan bir charIndexMap kullanarak, tekrar eden karakterleri hızlı bir şekilde tespit etmeyi sağlar. Bu sayede, zaman karmaşıklığı O(n) olurken, uzay karmaşıklığı da O(min(m, n)) olur. Burada n stringin uzunluğu ve m karakter sayısıdır. Yani, oldukça verimli bir çözüm sunmaktadır. Bu çözümü anlamak için, kod satırlarını adım adım takip etmeniz ve örnek girdilerle test etmeniz faydalı olacaktır. Daha ayrıntılı bir açıklama için buraya bakabilirsiniz.

Sonuç olarak, “En Uzun Tekrarlanmayan Karakter Alt Dizisi” problemi, kayan pencere tekniği kullanılarak verimli bir şekilde çözülebilir. Bu teknik, algoritma tasarımında sıklıkla kullanılan ve oldukça güçlü bir yöntemdir. Bu problem, algoritma ve veri yapıları öğrenimi için iyi bir örnek teşkil etmektedir. Umarım bu makale size yardımcı olmuştur. Daha fazla içerik için web sitemi ziyaret edebilirsiniz.

#Etiketler: LeetCode, JavaScript, En Uzun Tekrarlanmayan Karakter Alt Dizisi, Kayan Pencere Tekniği, Algoritma, Veri Yapıları, Programlama, Çözüm, Fatih Soysal