Sliding_window_practice_problems.md

1. Find the length of longest substring without repeating characters

def longest_substring(s1):
    n = len(s1)
    charSet = set()
    l = 0
    result = 0
    for r in range(n):
        while s1[r] in charSet:
            charSet.remove(s1[l])
            l += 1
        charSet.add(s1[r])
        result = max(result, r-l+1)
    return result

s = "abcabcbb"
print(longest_substring(s))

s = "bbbbb"
print(longest_substring(s))

---

2.Find the length of the longest substring without repeating characters along with the substring

def longest_substring_without_repeating_characters(s1):
    n = len(s1)
    l = 0
    charset = set()
    result = 0
    resstring = ""
    for r in range(n):
        while s1[r] in charset:
            charset.remove(s1[l])
            l += 1
        charset.add(s1[r])
        if (r-l+1) > result:
            result = r-l+1
            resstring = s1[l:r+1]
    return result, resstring

result, resultsubstring = longest_substring_without_repeating_characters("abababacabahgyvaba")
print(f"The length of the longest substring is {result} in {resultsubstring}")

---

3. Find the Longest substring with k distinct character

def longest_substring_with_k_distinct_char(s1, k):
    if k == 0 or not s1:
        return 0

    n = len(s1)
    l = 0
    map1 = {}
    maxLen = 0
    
    for r in range(n):
        map1[s1[r]] = map1.get(s1[r], 0) + 1
        while len(map1) > k:  # Changed from 2 to k
            map1[s1[l]] -= 1
            if map1[s1[l]] == 0:
                del map1[s1[l]]
            l += 1
            
        maxLen = max(maxLen, r - l + 1)
    return maxLen

result = longest_substring_with_k_distinct_char("abcabcaabbccdeft", 3)
print(result)

---

4. Find the longest substring with k distinct character along with the substring

def longest_substring_with_k_distinct_character(s1, k):
    n = len(s1)
    max_freq = {}
    res= ""
    max_len = 0
    l = 0
    for r in range(n):
        max_freq[s1[r]] = max_freq.get(s1[r],0)+1
        while len(max_freq) > k:
            max_freq[s1[l]] -= 1
            if max_freq[s1[l]] == 0:
                del max_freq[s1[l]]
            l += 1
        
        if (r-l+1) > max_len:
            max_len = r-l+1
            res = s1[l:r+1]
    return max_len, result_substring

max_length, result_substring = longest_substring_with_k_distinct_char("abcabcaabbccdeft", 3)
print(f"The length of the longest of the substring is {max_length} and the substring is {result_substring}")

---