LeetCode Problem #3: En Uzun Tekrarlanmayan Altdizi

“`html

LeetCode Problem #3: En Uzun Tekrarlanmayan Altdizi

LeetCode’un 3. problemi, “En Uzun Tekrarlanmayan Altdizi” (Longest Substring Without Repeating Characters) problemidir. Bu problem, verilen bir string içinde tekrar eden karakter içermeyen en uzun altdizinin uzunluğunu bulmayı gerektirir. Örneğin, “abcabcbb” stringi için en uzun tekrarlanmayan altdizi “abc” olup, uzunluğu 3’tür. Bu problemi çözmek için farklı yaklaşımlar kullanılabilir; ancak en yaygın ve etkili yöntemlerden biri kayan pencere (sliding window) algoritmasıdır.

Kayan Pencere Algoritması ile Çözüm

Kayan pencere algoritması, verilen string üzerinde iki işaretçi (pointer) kullanır: başlangıç ve bitiş. Başlangıç işaretçisi altdizinin başlangıcını, bitiş işaretçisi ise sonunu gösterir. Algoritma, bitiş işaretçisini sağa doğru hareket ettirerek stringi tarar. Eğer bitiş işaretçisinin gösterdiği karakter, mevcut altdizi içinde zaten varsa, başlangıç işaretçisi, tekrar eden karakteri altdiziden çıkarana kadar sola doğru hareket ettirilir. Bu işlem, her adımda en uzun tekrarlanmayan altdizinin uzunluğunu güncelleyerek devam eder.

Örneğin, “abcabcbb” stringi için algoritma şu şekilde çalışır:

1. Başlangıç ve bitiş işaretçileri “a” karakterinde başlar. Altdizi “a”, uzunluğu 1’dir.
2. Bitiş işaretçisi “b” ye hareket eder. Altdizi “ab”, uzunluğu 2’dir.
3. Bitiş işaretçisi “c” ye hareket eder. Altdizi “abc”, uzunluğu 3’tür.
4. Bitiş işaretçisi “a” ya hareket eder. “a” zaten altdizi içinde var. Başlangıç işaretçisi “a” yı altdiziden çıkarmak için “b” ye hareket eder. Yeni altdizi “bca”, uzunluğu 3’tür.
5. Bu şekilde devam ederek, en uzun tekrarlanmayan altdizi “abc” olarak bulunur ve uzunluğu 3 olarak kaydedilir.

Kod Örneği (Python)

def longest_substring_without_repeating_characters(s):
    n = len(s)
    ans = 0
    # mp stores the current index of a character
    mp = {}

    i = 0
    for j in range(n):
        if s[j] in mp:
            i = max(mp[s[j]], i)

        ans = max(ans, j - i + 1)
        mp[s[j]] = j + 1

    return ans

# Örnek kullanım:
string = "abcabcbb"
uzunluk = longest_substring_without_repeating_characters(string)
print(f"'{string}' stringinin en uzun tekrarlanmayan altdizinin uzunluğu: {uzunluk}")

Bu kod örneği, kayan pencere algoritmasını kullanarak problemi etkili bir şekilde çözer. Ancak, daha karmaşık senaryolar için daha optimize çözümler gerekebilir. Örneğin, çok büyük stringler için daha verimli veri yapıları kullanılabilir.

Sonuç olarak, LeetCode Problem #3, temel algoritma kavramlarını anlamak ve uygulamak için mükemmel bir örnektir. Kayan pencere algoritması, bu problem için oldukça etkili bir çözüm sunar ve daha geniş bir yelpazede benzer problemlerin çözümünde kullanılabilir. Bu problem, veri yapıları ve algoritmalar konusundaki bilgilerinizi geliştirmenize yardımcı olacaktır. Daha fazla bilgi için buraya bakabilirsiniz. Kendi algoritma ve veri yapıları çalışmalarınız için de fatihsoysal.com sitesini ziyaret edebilirsiniz.

#Etiketler: LeetCode, Problem 3, En Uzun Tekrarlanmayan Altdizi, Kayan Pencere Algoritması, Sliding Window, Python, Algoritma, Veri Yapıları, Programlama, Fatih Soysal

“`