Strings & Hashing (Medium)Master string manipulation and hashing techniques including anagrams, substrings, and palindromes.

171. Longest Substring Without Repeating Characters

Problem Statement

Given a string `s`, find the length of the **longest substring** without repeating characters. **Example 1:** ``` Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. ``` **Example 2:** ``` Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. ```

Approach

1. **Sliding Window**: Use a window defined by `left` and `right` pointers. 2. **Tracking**: Use a hash map (or dictionary) to store the last seen index of each character. 3. **Logic**: * Iterate with `right`. * If `s[right]` is in map and its index is >= `left`, it means we found a repeat inside the current window. * Move `left` to `map[s[right]] + 1`. * Update `map[s[right]] = right`. * Update `max_len = max(max_len, right - left + 1)`.

Solution

`def lengthOfLongestSubstring(s):
    char_map = {

172. Longest Palindromic Substring

Problem Statement

Given a string `s`, return the longest palindromic substring in `s`. **Example 1:** ``` Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. ``` **Example 2:** ``` Input: s = "cbbd" Output: "bb" ```

Approach

1. **Expand Around Center**: A palindrome mirrors around its center. 2. **Centers**: A palindrome can have a center at a specific character (odd length like "aba", center 'b') or between two characters (even length like "abba", center between 'b's). 3. **Approach**: * Iterate through each character `i`. * Expand for odd case: `expand(i, i)`. * Expand for even case: `expand(i, i + 1)`. * Keep track of the max length and start index.

Solution

def longestPalindrome(s):
    if not s: return ""
    start = 0
    max_len = 0
    
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1  # Length is (right-1) - (left+1) + 1
        
    for i in range(len(s)):
        len1 = expand(i, i)
        len2 = expand(i, i + 1)
        length = max(len1, len2)
        
        if length > max_len:
            max_len = length
            # Calculate new start based on center i
            # If length is odd (len1), start is i - length//2
            # If length is even (len2), start is i - (length-1)//2
            start = i - (length - 1) // 2
            
    return s[start : start + max_len]

173. Group Anagrams

Problem Statement

Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. **Example 1:** ``` Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] ```

Approach

1. **Key Idea**: Anagrams have the same sorted characters. "eat" -> "aet", "tea" -> "aet". 2. **Hashing**: Use a dictionary where the key is the sorted tuple of characters, and value is the list of original strings. 3. **Optimization**: Instead of sorting (O(N log N)), you can use a character count tuple (26 zeros) as the key if strings only contain lowercase English letters.

Solution

`def groupAnagrams(strs):
    anagram_map = {

174. Valid Parentheses

Problem Statement

` Given a string `s` containing just the characters '(', ')', '{', '

Approach

1. **Stack**: Ideal data structure for matching nested pairs. 2. **Logic**: * Iterate through characters. * If open bracket, push to stack. * If close bracket, check if stack is empty (invalid) or if top matches. * If matches, pop. If not, invalid. * At the end, stack must be empty.

Solution

`def isValid(s):
    stack = []
    mapping = {")": "(", "

175. String Compression

Problem Statement

Given an array of characters `chars`, compress it using the following algorithm: Begin with an empty string s. For each group of consecutive repeating characters in chars: * If the group's length is 1, append the character to s. * Otherwise, append the character followed by the group's length. The compressed string s should not be returned separately, but instead, be stored **in the input character array chars**. Note that group lengths that are 10 or longer will be split into multiple characters in chars. Return the new length of the array. **Example 1:** ``` Input: chars = ["a","a","b","b","c","c","c"] Output: 6, chars = ["a","2","b","2","c","3"] ```

Approach

1. **In-place Modification**: We need to write to `chars` directly. 2. **Two Pointers**: * `write`: Position to write the next character/count. * `read`: Current position scanning the array. 3. **Logic**: * Scan with `read`. Find the end of the current consecutive block. * Write the character at `chars[write]`. * If count > 1, convert count to string and write each digit to `chars`, incrementing `write`.

Solution

def compress(chars):
    write = 0
    read = 0
    n = len(chars)
    
    while read < n:
        char = chars[read]
        count = 0
        
        # Count consecutive duplicates
        while read < n and chars[read] == char:
            read += 1
            count += 1
            
        # Write character
        chars[write] = char
        write += 1
        
        # Write count if > 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
                
    return write

176. Decode String

Problem Statement

Given an encoded string, return its decoded string. The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. Note that `k` is guaranteed to be a positive integer. **Example 1:** ``` Input: s = "3[a]2[bc]" Output: "aaabcbc" ``` **Example 2:** ``` Input: s = "3[a2[c]]" Output: "accaccacc" ```

Approach

1. **Nested Structure**: Suggests Stack or Recursion. 2. **Stack Approach**: * Iterate through string. * If digit: parse full number. * If '[': push current number and current working string to stack. Reset them. * If ']': pop (prev_num, prev_str). Current string becomes `prev_str + prev_num * current_string`. * Else (char): append to current string.

Solution

def decodeString(s):
    stack = []
    curr_str = ""
    curr_num = 0
    
    for char in s:
        if char.isdigit():
            curr_num = curr_num * 10 + int(char)
        elif char == "[":
            stack.append((curr_str, curr_num))
            curr_str = ""
            curr_num = 0
        elif char == "]":
            prev_str, num = stack.pop()
            curr_str = prev_str + num * curr_str
        else:
            curr_str += char
            
    return curr_str

Back

Strings & Hashing (Medium) / 171. Longest Substring Without Repeating Characters

00:00

1/6

171. Longest Substring Without Repeating Characters

Medium

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

1
Sliding Window: Use a window defined by left and right pointers.
2
Tracking: Use a hash map (or dictionary) to store the last seen index of each character.
3
Logic:
4
Iterate with right.
5
If s[right] is in map and its index is >= left, it means we found a repeat inside the current window.
6
Move left to map[s[right]] + 1.
7
Update map[s[right]] = right.
8
Update max_len = max(max_len, right - left + 1).

PYTHON PLAYGROUND

⏳ Loading editor…