DEV Community: Hommies

LeetCode Solution: 5. Longest Palindromic Substring

Hommies — Sat, 16 May 2026 18:44:09 +0000

Longest Palindromic Substring: A Core String Algorithm Explained

Welcome to another deep dive into a classic LeetCode problem! Today, we're tackling Problem 5: Longest Palindromic Substring. This problem is a fantastic way to sharpen your string manipulation and algorithmic thinking skills.

Problem Explanation

Given a string s, our goal is to find and return the longest substring within s that is a palindrome.

What's a palindrome? It's a sequence of characters that reads the same forwards and backward (e.g., "madam", "racecar", "level").
What's a substring? It's a contiguous sequence of characters within a string (e.g., for "apple", "app" is a substring, but "ale" is not).

Let's look at the examples:

Example 1:
- Input: s = "babad"
- Output: "bab"
- Explanation: "aba" is also a valid answer of the same length.
Example 2:
- Input: s = "cbbd"
- Output: "bb"

The string s will contain only digits and English letters, and its length will be between 1 and 1000 characters.

Intuition

The core idea behind finding palindromes is that they expand symmetrically from a center point. Think about "racecar" – the 'e' is the center, and 'c' expands to 'r'. Or "abba" – the center is between the two 'b's, and 'a' expands to 'a'.

This insight simplifies our search: instead of checking every single substring for palindromic properties (which is O(N^3) or O(N^2) with an O(N) check), we can iterate through every possible "center" and try to expand outwards.

There are two types of centers we need to consider:

Single character center: For palindromes with an odd length (e.g., "b*ab", "ra*cecar"). Here, s[i] itself is the center.
Two character center: For palindromes with an even length (e.g., "bb", "a*bb*a"). Here, s[i] and s[i+1] form the center.

Approach

We'll use an "Expand Around Center" approach:

Initialize: Keep track of the start and end indices of the longest palindrome found so far. Initialize them to 0, 0 (assuming a single character is the shortest possible palindrome).
Iterate Through Centers: Loop through each character in the string using an index i. Each i will serve as a potential center.
Expand for Odd Length Palindromes: Call a helper function expand_around_center(s, i, i). This tries to expand a palindrome assuming s[i] is its sole center.
Expand for Even Length Palindromes: Call the helper function expand_around_center(s, i, i + 1). This tries to expand a palindrome assuming s[i] and s[i+1] are its two central characters.
Helper Function expand_around_center(s, left, right):
- This function takes the string s and two indices, left and right.
- It expands outwards: left moves to the left (left-1) and right moves to the right (right+1).
- This expansion continues as long as left is within bounds (>= 0), right is within bounds (< len(s)), and the characters at s[left] and s[right] are equal.
- Once the loop terminates (either due to bounds or mismatch), the length of the palindrome found is right - left - 1.
Update Longest Palindrome: After getting len1 (odd center) and len2 (even center), determine max_len = max(len1, len2). If max_len is greater than the length of our current longest palindrome (end - start + 1), then update start and end.
- To calculate the new start and end from i and max_len:
  - start = i - (max_len - 1) // 2
  - end = i + max_len // 2
Return Result: After iterating through all possible centers, return the substring s[start : end + 1].

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start = 0
        end = 0

        # Helper function to expand around a given center
        def expand_around_center(s: str, left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # When the loop finishes, left and right are one step beyond the palindrome boundaries.
            # So, the length is (right - 1) - (left + 1) + 1 = right - left - 1
            return right - left - 1

        # Iterate through each character, treating it as a potential center
        for i in range(len(s)):
            # Case 1: Odd length palindrome (center is s[i])
            len1 = expand_around_center(s, i, i)

            # Case 2: Even length palindrome (center is s[i] and s[i+1])
            len2 = expand_around_center(s, i, i + 1)

            # Get the maximum length found from these two expansions
            max_len = max(len1, len2)

            # If this palindrome is longer than our current longest
            if max_len > end - start + 1:
                # Calculate the new start and end indices
                # For an odd length palindrome centered at i: start = i - (length-1)/2, end = i + (length-1)/2
                # For an even length palindrome centered between i and i+1: start = i - (length/2 - 1), end = i + length/2
                # The combined formula works for both:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        # Return the longest palindromic substring
        return s[start : end + 1]

Time & Space Complexity Analysis

Time Complexity: O(N^2)
- The main loop iterates N times, where N is the length of the string s.
- Inside the loop, expand_around_center is called twice. In the worst case, expand_around_center might traverse the entire string (e.g., for "aaaa...a").
- Thus, each call to expand_around_center takes O(N) time.
- Overall complexity: N * O(N) = O(N^2).
Space Complexity: O(1)
- We are only using a few variables (start, end, i, len1, len2, max_len, left, right) to store indices and lengths.
- The space used does not grow with the input string size.

Key Takeaways

Palindromes and Symmetry: The inherent symmetry of palindromes is key to efficient algorithms.
Expand Around Center: This is a powerful technique for palindrome problems, allowing us to find palindromes by growing them from every possible middle point.
Handling Odd and Even Lengths: Remember to consider both types of palindromes (odd-length with a single character center, and even-length with a two-character center).

This "Expand Around Center" approach is generally simpler to implement than dynamic programming solutions for this problem, while achieving the same O(N^2) time complexity.

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:13:54

LeetCode Solution: 4. Median of Two Sorted Arrays

Hommies — Sat, 16 May 2026 18:42:44 +0000

Unlock the Median Magic: Diving into Two Sorted Arrays!

Hey LeetCoders and aspiring developers! 👋

Today, we're tackling a classic LeetCode challenge that often pops up in interviews: 4. Median of Two Sorted Arrays. Don't let the "Hard" tag intimidate you! While the optimal solution is quite advanced, we'll walk through a very intuitive, step-by-step approach that makes perfect sense for beginners. Let's conquer this one together!

🚀 Problem Explanation: What are we actually doing?

Imagine you have two separate lists of numbers, nums1 and nums2, and here's the crucial part: both are already sorted! Your mission is to find the median of all the numbers if you were to combine these two lists into one big, sorted list.

What's a median?

If you have an odd number of elements in a sorted list, the median is simply the middle element. For [1, 2, 3], the median is 2.
If you have an even number of elements, the median is the average of the two middle elements. For [1, 2, 3, 4], the median is (2 + 3) / 2 = 2.5.

The problem throws a curveball: it asks for an overall runtime complexity of O(log(m+n)). We'll discuss this after exploring a more straightforward solution.

Example 1:

nums1 = [1,3], nums2 = [2]
If merged and sorted: [1,2,3]
Median: 2 (middle element)

Example 2:

nums1 = [1,2], nums2 = [3,4]
If merged and sorted: [1,2,3,4]
Median: (2+3)/2 = 2.5 (average of two middle elements)

🤔 Intuition: The "Aha!" Moment

The simplest way to find the median of two sorted arrays is to just... merge them! If we combine nums1 and nums2 into a single, sorted array, finding the median becomes trivial.

However, actually building a new merged array takes O(m+n) space and time. Can we do it without fully merging? Yes! We only need to find the element(s) at the median position(s). We can simulate the merge process by using two pointers, one for each array, and pick elements one by one until we reach the median position.

Think of it like this: you're trying to find the k-th smallest element in the combined list. Since the arrays are sorted, you can always compare the current smallest elements from nums1 and nums2 to find the overall next smallest element. We'll just keep doing this until we've "counted" up to our median position.

🪜 Approach: Simulating the Merge (O(m+n) Time)

Let's break down the step-by-step logic for our beginner-friendly O(m+n) approach:

Calculate Total Length & Median Positions:
- Find the total number of elements: total_len = len(nums1) + len(nums2).
- Determine if we need one median element (odd total_len) or two (even total_len). We'll need to iterate enough times to identify these elements.
Initialize Pointers and Median Candidates:
- Use two pointers, i for nums1 and j for nums2, both starting at 0.
- Introduce two variables, m1 and m2. m1 will store the current element identified as we iterate through the "merged" sequence. m2 will store the previous m1 value. This is crucial for when we need to average two middle elements (even total_len).
Iterate to the Median Position(s):
- We need to find elements up to total_len // 2 + 1. This ensures that for an even total_len, we capture both (total_len // 2) - 1 and (total_len // 2) elements (0-indexed).
- In each iteration:
  - First, m2 = m1. The current m1 becomes the "second to last" median candidate.
  - Then, compare the elements nums1[i] and nums2[j].
    - If nums1[i] is smaller (or nums2 is exhausted), pick nums1[i], assign it to m1, and increment i.
    - Otherwise (if nums2[j] is smaller or nums1 is exhausted), pick nums2[j], assign it to m1, and increment j.
Calculate and Return the Median:
- After the loop finishes, m1 will hold the element at total_len // 2 (0-indexed) and m2 will hold the element at (total_len // 2) - 1.
- If total_len is odd, m1 is our median.
- If total_len is even, the median is the average of m1 and m2.

This approach effectively "walks" through the merged sorted array without actually building it, stopping exactly when it finds the necessary median elements.

💻 Code: The O(m+n) Merge-Like Solution (Python)

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        total_len = m + n

        # m1 will store the element at the current "median" position
        # m2 will store the element at the "median-1" position (for even total_len)
        m1, m2 = 0, 0 

        i, j = 0, 0 # Pointers for nums1 and nums2

        # Iterate (m + n) // 2 + 1 times to find the median element(s)
        # We need to iterate one more time than total_len // 2 for even arrays
        # to capture both m1 and m2 correctly.
        for count in range(total_len // 2 + 1):
            m2 = m1 # m2 takes the value m1 had in the previous iteration

            # Logic to pick the next smallest element from either nums1 or nums2
            if i < m and (j >= n or nums1[i] < nums2[j]):
                m1 = nums1[i]
                i += 1 
            else: # j < n and (i >= m or nums2[j] <= nums1[i])
                m1 = nums2[j]
                j += 1

        # Check if the sum of n and m is odd.
        if (n + m) % 2 == 1:
            return float(m1)
        else:
            ans = float(m1) + float(m2)
            return ans / 2.0

⏱️ Time & Space Complexity Analysis

For the O(m+n) solution we just explored:

Time Complexity: O(m+n)
- We iterate through the arrays up to (m+n)/2 + 1 times in the worst case. This is directly proportional to the total number of elements.
Space Complexity: O(1)
- We only use a few extra variables (m1, m2, i, j, total_len). We don't create any new arrays proportional to the input size.

A Note on the O(log(m+n)) Requirement:
The problem statement does ask for an O(log(m+n)) runtime complexity. This typically points to a more advanced solution involving binary search on partitions. That approach is significantly more complex and often involves finding a "split point" in both arrays such that the elements to the left of the split form the lower half of the merged array, and elements to the right form the upper half.

While our O(m+n) solution is intuitive and a great starting point, mastering the O(log(m+n)) binary search approach is a fantastic next step once you're comfortable with this basic idea!

🌟 Key Takeaways

Simulate, Don't Always Build: For problems involving sorted arrays and finding specific elements (like the median or k-th smallest), you often don't need to physically merge them. Simulating the merge with pointers is efficient.
Median Logic: Remember the difference between odd and even total lengths for calculating the median. Keeping track of two "median candidate" variables (m1 and m2) helps simplify this.
Complexity Matters: Always be aware of the optimal time complexity required for a problem. While an O(m+n) solution is often a good first step, understanding the O(log(m+n)) binary search approach for this specific problem is key for interviews.

Happy coding, and keep practicing! You're doing great!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:12:16

LeetCode Solution: 3. Longest Substring Without Repeating Characters

Hommies — Sat, 16 May 2026 17:38:35 +0000

Sliding into Success: Solving LeetCode 3 - Longest Substring Without Repeating Characters

Hey there, aspiring competitive programmers and curious coders!

Today, we're diving into a classic LeetCode problem that's a fantastic introduction to a super useful technique: the Sliding Window. It's problem #3, "Longest Substring Without Repeating Characters," and it's a rite of passage for many!

Don't let the name intimidate you. By the end of this post, you'll not only understand it but also appreciate the elegance of its solution.

Problem Explanation: What are we actually trying to find?

The problem asks us to find the length of the longest substring within a given string s that doesn't have any repeating characters.

Let's break down some keywords:

String s: This is our input, like "abcabcbb" or "pwwkew".
Substring: This is a contiguous sequence of characters within a string. For example, in "abc", "a", "ab", "bc", "abc" are substrings. "ac" is not a substring because the characters aren't consecutive.
Without repeating characters: Every character in our substring must be unique. If we see 'a', we can't have another 'a' in the same substring.

Let's look at the examples:

s = "abcabcbb"
- "abc" is a substring without repeating characters (length 3).
- "bca" is also a substring without repeating characters (length 3).
- The longest such substring has a length of 3.
s = "bbbbb"
- "b" is the longest substring without repeating characters (length 1).
s = "pwwkew"
- "pw" (length 2)
- "wke" (length 3) - This is our winner!
- "kew" (length 3) - Another winner!
- IMPORTANT: "pwke" is not a substring, it's a subsequence. Remember, substrings must be contiguous. "wke" is valid because 'w', 'k', 'e' are consecutive.

Our goal is to return just the length of this longest unique-character substring.

Intuition: The "Aha!" Moment

Imagine you're looking at a street. You want to find the longest stretch of unique houses (characters). You start walking, adding each new house you see to your mental list.

If you see a house you've already listed, you know your current unique stretch has ended at or before this duplicate.
To continue, you can't just skip the duplicate. You need to "forget" houses from the beginning of your current stretch until the duplicate is no longer in your list. Then, you can add the current house and keep walking.

This "walking" and "forgetting" sounds like a Sliding Window! We'll have two pointers: left and right.

right expands our window, bringing new characters in.
left shrinks our window when we encounter a duplicate, removing characters from the start until the duplicate is gone.

At each step, we'll keep track of the maximum length our window has ever achieved.

Approach: Building Our Sliding Window

We'll use two pointers, left and right, to define our current "window" (substring). We also need a way to quickly check if a character is already in our current window. A Set (or HashSet in some languages) is perfect for this, as it allows for O(1) average time complexity for add, remove, and check operations.

Here's the step-by-step logic:

Initialize:
- left = 0: This pointer marks the beginning of our current unique substring.
- max_length = 0: This will store the maximum length we've found so far.
- char_set = set(): An empty set to store characters currently within our window [left, right].
Iterate with right pointer:
- We'll use a for loop, letting right traverse the input string s from 0 to len(s) - 1. This pointer expands our window to the right.
Check for Duplicates:
- Inside the loop, before adding s[right] to our char_set, we check if s[right] is already in char_set.
- If s[right] IS in char_set (duplicate found):
  - This means our current window s[left...right-1] has a duplicate if s[right] is added.
  - To resolve this, we need to shrink our window from the left side.
  - We enter a while loop:
    - Remove s[left] from char_set.
    - Increment left by 1.
    - Repeat this until s[right] is no longer in char_set. This ensures our window s[left...right-1] is unique before we add s[right].
- If s[right] IS NOT in char_set (unique character):
  - Great! We can safely add s[right] to char_set.
Update max_length:
- After s[right] has been added (and duplicates handled if any), our current window s[left...right] is guaranteed to be unique.
- The length of this current unique window is right - left + 1.
- Update max_length = max(max_length, right - left + 1).
Return:
- After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters. Return max_length.

Let's walk through s = "abcabcbb":

`right`	`s[right]`	`char_set` (before add)	Duplicate?	Actions (if duplicate)	`char_set` (after add)	`left`	Current Length (`right - left + 1`)	`max_length`
0	'a'	{}	No	-	{'a'}	0	1	1
1	'b'	{'a'}	No	-	{'a', 'b'}	0	2	2
2	'c'	{'a', 'b'}	No	-	{'a', 'b', 'c'}	0	3	3
3	'a'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=1`	{'b', 'c', 'a'}	1	3 (`3 - 1 + 1`)	3
4	'b'	{'b', 'c', 'a'}	Yes	`char_set.remove('b')`, `left=2`	{'c', 'a', 'b'}	2	3 (`4 - 2 + 1`)	3
5	'c'	{'c', 'a', 'b'}	Yes	`char_set.remove('c')`, `left=3`	{'a', 'b', 'c'}	3	3 (`5 - 3 + 1`)	3
6	'b'	{'a', 'b', 'c'}	Yes	`char_set.remove('a')`, `left=4`	{'b', 'c', 'b'}	4	3 (`6 - 4 + 1`)	3
				`char_set.remove('b')`, `left=5`	{'c', 'b'}	5	2 (`6 - 5 + 1`)	3

Final max_length is 3. This trace confirms the logic!

Code: Bringing it to life with Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # A set to keep track of characters in the current window
        char_set = set()

        # Left pointer of the sliding window
        left = 0

        # Variable to store the maximum length found so far
        max_length = 0

        # Right pointer iterates through the string
        for right in range(len(s)):
            # If the character at 'right' is already in our set,
            # it means we have a duplicate within the current window.
            # We need to shrink the window from the 'left' until the duplicate is removed.
            while s[right] in char_set:
                char_set.remove(s[left]) # Remove the character at 'left' from the set
                left += 1                # Move the 'left' pointer one step to the right

            # Now that the current character s[right] is guaranteed to be unique
            # in the window [left...right-1], we can add it to our set.
            char_set.add(s[right])

            # Update the maximum length found.
            # The current window length is (right - left + 1).
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

Time Complexity: O(N)
- Both the left and right pointers traverse the string s at most once.
- The right pointer moves N times.
- The left pointer also moves at most N times across all iterations of the outer loop.
- Set operations (add, remove, check in) take O(1) average time.
- Therefore, the total time complexity is linear, O(N), where N is the length of the string s.
Space Complexity: O(min(M, N))
- We use a char_set to store unique characters within the window.
- In the worst case, if all characters in the string are unique (e.g., "abcdefg"), the set will store N characters.
- However, if the character set is limited (e.g., lowercase English letters, M=26), the set will store at most M characters.
- So, the space complexity is bounded by the smaller of the string's length N and the size of the character set M.

Key Takeaways

Sliding Window Technique: This problem is a prime example of the "sliding window" pattern, which is incredibly useful for array/string problems involving a contiguous subsegment. It helps optimize solutions from O(N^2) (e.g., checking every possible substring) to O(N).
Set for Uniqueness Checks: Using a hash set (set in Python) is crucial for efficient O(1) average-time lookups, insertions, and deletions, which allows the sliding window to perform optimally.
Two Pointers (Left and Right): The left pointer helps shrink the window when a condition is violated (duplicate found), while the right pointer expands it.

Keep practicing, and you'll master these patterns in no time! Happy coding!

Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 23:08:20

LeetCode Solution: 3. Longest Substring Without Repeating Characters

Hommies — Sat, 16 May 2026 17:30:51 +0000

Cracking LeetCode 3: The Longest Substring Without Repeating Characters (A Sliding Window Adventure!)

Hey Devs! 👋 Ever stumbled upon a LeetCode problem that looks simple but hides a powerful algorithmic pattern? Today, we're diving into LeetCode problem #3, "Longest Substring Without Repeating Characters." This classic problem is a fantastic introduction to a super common and efficient technique: the Sliding Window.

Don't worry if that sounds intimidating – we'll break it down piece by piece, like LEGOs! By the end of this post, you'll not only understand the solution but also gain a valuable tool for tackling similar string and array problems. Let's get started!

The Problem: Unpacking "Longest Substring Without Repeating Characters"

Imagine you're given a string, like "abcabcbb". Your mission, should you choose to accept it, is to find the longest substring within it that doesn't have any character repeated.

Let's clarify some terms:

Substring: A contiguous sequence of characters within a string. "abc" is a substring of "abcabcbb", but "acb" is not.
Without Repeating Characters: Every character in our chosen substring must be unique. No 'a' appearing twice, no 'b' appearing twice, etc.

Examples to make it crystal clear:

Input: s = "abcabcbb"
- "abc" is a substring without repeating characters (length 3).
- "bca" is also valid (length 3).
- "abcab" is NOT valid because 'a' and 'b' repeat.
- The longest one we can find is "abc" (or "bca", "cab"), with a length of 3.
Input: s = "bbbbb"
- The longest substring without repeating characters is just "b" (length 1).
Input: s = "pwwkew"
- "pwke" is NOT a substring; it's a subsequence (characters appear in order but not necessarily contiguously).
- "wke" IS a substring without repeating characters (length 3).
- "pww" has repeating 'w'.
- The longest is "wke" (length 3).

The goal is to return just the length of this longest unique substring.

The Intuition: Why a "Sliding Window"?

If you're new to competitive programming, your first thought might be: "Let's check every possible substring!" And that's a valid starting point. You could have two loops, i and j, generating all substrings s[i:j+1], and for each, check if it has repeating characters. This would work, but it's pretty slow (think O(N^3) or O(N^2) depending on how you check uniqueness). Can we do better? Absolutely!

The "aha!" moment comes when you realize that if you have a substring s[left...right] that contains duplicate characters, you don't need to re-examine the entire string from scratch. You just need to adjust your current substring until it becomes valid again.

This is where the Sliding Window technique shines! Imagine a window "sliding" over the string. This window represents our current substring.

We try to expand the window from the right.
If we add a character that causes a duplicate, we shrink the window from the left until the duplicate is gone.
At each valid step, we keep track of the maximum length our window has achieved.

The Approach: Two Pointers and a Set

Let's formalize our sliding window approach using two pointers, left and right, and a set to efficiently track characters within our current window.

Initialize:
- max_length = 0: This will store our answer.
- left = 0: This pointer marks the beginning of our current unique substring window.
- char_set = set(): This set will hold all characters currently inside our s[left...right] window. Sets are perfect because they only store unique items and offer super fast add, remove, and in (contains) operations (average O(1) time complexity).
Iterate with the right pointer:
- We'll use a for loop with right iterating from 0 to len(s) - 1. This pointer expands our window to the right.
Check for Duplicates and Shrink the Window:
- Inside the loop, before adding s[right] to our char_set, we need to check if s[right] is already in char_set.
- If s[right] is ALREADY in char_set: This means we have a duplicate! Our current window s[left...right-1] was unique, but s[right] broke the rule.
  - To fix this, we need to shrink the window from the left.
  - We repeatedly remove s[left] from char_set and increment left until s[right] is no longer a duplicate within our window.
  - Think of it as kicking out characters from the left until the culprit (the first instance of the duplicate) is gone.
Expand the Window and Update Max Length:
- Once s[right] is guaranteed to be unique within our current (possibly shrunken) window, add s[right] to char_set.
- Now, our current window s[left...right] is valid (all unique characters). Calculate its length: right - left + 1.
- Update max_length = max(max_length, right - left + 1).
Return max_length: After the right pointer has traversed the entire string, max_length will hold the length of the longest substring without repeating characters.

Let's trace s = "abcabcbb":

`right`	`s[right]`	`char_set` (before `s[right]` check)	`s[right]` in `char_set`?	`char_set` (after fix)	`left` (after fix)	`char_set` (after add `s[right]`)	Current Window (`s[left...right]`)	Current Length	`max_length`
`0`	`a`	`{}`	`False`	`{}`	`0`	`{a}`	`a`	`1`	`1`
`1`	`b`	`{a}`	`False`	`{a}`	`0`	`{a, b}`	`ab`	`2`	`2`
`2`	`c`	`{a, b}`	`False`	`{a, b}`	`0`	`{a, b, c}`	`abc`	`3`	`3`
`3`	`a`	`{a, b, c}`	`True` (a repeats)	`{b, c}`	`1`	`{b, c, a}`	`bca`	`3`	`3`
`4`	`b`	`{b, c, a}`	`True` (b repeats)	`{c, a}`	`2`	`{c, a, b}`	`cab`	`3`	`3`
`5`	`c`	`{c, a, b}`	`True` (c repeats)	`{a, b}`	`3`	`{a, b, c}`	`abc`	`3`	`3`
`6`	`b`	`{a, b, c}`	`True` (b repeats)	`{c}`	`5`	`{c, b}`	`cb`	`2`	`3`
`7`	`b`	`{c, b}`	`True` (b repeats)	`{}`	`7`	`{b}`	`b`	`1`	`3`

Finally, max_length is 3! This matches the example.

The Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set() # To store characters in the current window
        left = 0         # Left pointer of the sliding window
        max_length = 0   # Stores the maximum length found so far

        for right in range(len(s)):
            # While the character at 'right' is already in our set (duplicate detected)
            while s[right] in char_set:
                # Remove the character at 'left' from the set
                char_set.remove(s[left])
                # Move the 'left' pointer to shrink the window
                left += 1

            # Add the current character at 'right' to the set
            # Now, the window s[left...right] is guaranteed to have unique characters
            char_set.add(s[right])

            # Update the maximum length found
            max_length = max(max_length, right - left + 1)

        return max_length

Time & Space Complexity Analysis

This is where the sliding window truly shines!

Time Complexity: O(N)
- The right pointer iterates through the string s exactly once, performing N steps.
- The left pointer also iterates through the string at most once (it only moves forward).
- Each character is added to the char_set once and removed from the char_set at most once.
- set operations (add, remove, check in) take average O(1) time.
- Therefore, the total time complexity is linear, O(N), where N is the length of the string s. This is super efficient!
Space Complexity: O(min(N, M))
- char_set stores characters from the current window.
- In the worst case, if all characters are unique, the set could store up to N characters (where N is len(s)).
- However, the maximum size of the char_set is also limited by the size of the character set (e.g., 26 for lowercase English letters, 128 for ASCII, 256 for extended ASCII). Let M be the size of the alphabet.
- So, the space complexity is O(min(N, M)). For typical interview problems dealing with ASCII characters, this is often considered O(1) constant space because M (e.g., 128 or 256) is a fixed constant regardless of the input string's length.

Key Takeaways

Sliding Window Power: This problem is a perfect introduction to the sliding window pattern. Remember it for problems involving finding optimal subarrays or substrings.
Two Pointers: The left and right pointers are crucial for defining and moving the window efficiently.
Hash Set (Set) for Uniqueness: A set is your best friend when you need to quickly check for the presence of an element and ensure uniqueness. Its O(1) average time complexity for lookups, insertions, and deletions is key to the overall efficiency.
Distinguish Substring vs. Subsequence: Always pay attention to whether the problem asks for a substring (contiguous) or a subsequence (order preserved, not necessarily contiguous).

Congratulations! You've successfully navigated one of LeetCode's most popular problems and added the powerful Sliding Window technique to your algorithmic toolkit. Keep practicing, and these patterns will become second nature!

Published by p1Hzd8mRM8 on 2026-05-16 23:00:35

LeetCode Solution: 2. Add Two Numbers

Hommies — Sat, 16 May 2026 17:28:37 +0000

🚀 Cracking LeetCode #2: Adding Two Numbers Like a Pro (with Linked Lists!) 🚀

Hey there, future coding rockstars! 👋 Today, we're diving into a LeetCode classic that often stumps beginners but is incredibly satisfying once you "get" it. We're talking about LeetCode Problem #2: Add Two Numbers.

This problem is a fantastic introduction to manipulating linked lists and thinking about how computers handle fundamental operations like arithmetic. Ready to conquer it? Let's go!

The Problem Explained: Adding Numbers, But Backwards! 🤯

Imagine you want to add two big numbers, like 342 and 465. Normally, you'd write them down and add them from right to left (units, tens, hundreds, etc.), carrying over any extra digits.

Now, imagine these numbers aren't stored as regular integers but as linked lists. If you're new to linked lists, think of them as a chain of boxes (nodes), where each box holds a value and points to the next box in the chain.

The twist? The digits are stored in reverse order!

l1 = [2,4,3] actually represents the number 342. (3 -> 4 -> 2, but read from the head: 2 is units, 4 is tens, 3 is hundreds).
l2 = [5,6,4] actually represents the number 465.

Our goal is to add these two numbers (342 + 465) and return their sum (807) also as a linked list in reverse order: [7,0,8].

Let's look at the examples:

Example 1:
Input: l1 = [2,4,3] (342), l2 = [5,6,4] (465)
Output: [7,0,8] (807)
Explanation: 2 + 5 = 7. 4 + 6 = 10 (0 with carry 1). 3 + 4 + 1 (carry) = 8. So, [7, 0, 8].

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0.

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: This one shows longer lists and the need to handle a final carry! 9,999,999 + 9,999 = 10,009,998.

The "Aha!" Moment: Mimicking Manual Addition 💡

The key to solving this problem lies in realizing that since the digits are already in reverse order, the head of each linked list contains the least significant digit (the "ones" place). This is exactly where we start when we add numbers by hand!

So, the "aha!" moment is: we can simply iterate through both linked lists simultaneously, adding digits just like we would with pen and paper.

For each "place value":

Add the corresponding digits from l1 and l2.
Don't forget to add any carry from the previous addition!
The sum of these three numbers (digit1 + digit2 + carry) will give us a total_sum.
The new digit for our result list will be total_sum % 10 (the remainder when divided by 10).
The new carry for the next iteration will be total_sum // 10 (the quotient when divided by 10).

We continue this process until we've gone through both lists and handled any final carry.

The Step-by-Step Approach 🚶‍♂️

Let's break down the logic into concrete steps:

Initialize a Dummy Head: Create a dummy node. This is a common trick with linked lists! It acts as a placeholder for the beginning of our result list. We'll eventually return dummy.next to skip this placeholder.
Current Pointer for Result: Create a res pointer and point it to dummy. This res pointer will move along as we build our new linked list.
Initialize Carry: Set a carry variable to 0. This will store any carry-over digit from our additions.
Loop Until Done: We need to keep adding as long as there are digits in l1, digits in l2, or a carry remaining. So, our loop condition will be while l1 or l2 or carry:.
Get Current Digits:
- If l1 exists, get its val. Otherwise, consider it 0.
- If l2 exists, get its val. Otherwise, consider it 0.
- This handles lists of unequal lengths gracefully.
Calculate Sum: total_sum = val1 + val2 + carry.
New Digit and New Carry:
- The digit for our new node is total_sum % 10.
- The carry for the next iteration is total_sum // 10.
Create and Append New Node:
- Create a new ListNode with the calculated digit.
- Append this new node to our result list: res.next = new_node.
- Move our res pointer forward: res = res.next.
Advance Input Pointers:
- If l1 is not None, move l1 = l1.next.
- If l2 is not None, move l2 = l2.next.
Return Result: Once the loop finishes, return dummy.next. This skips our initial placeholder node and gives us the actual head of our sum list.

This approach perfectly mimics how we'd add numbers by hand, ensuring we handle carries and lists of different lengths.

The Code 🧑‍💻

Here's the Python implementation based on our approach:

# Definition for singly-linked list.
# This part is usually provided by LeetCode or you define it yourself.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        # 1. Initialize a dummy head for the result list
        dummy_head = ListNode()
        # 2. 'current' pointer to build the result list
        current = dummy_head 

        # 3. Initialize carry to 0
        carry = 0

        # 4. Loop as long as there are digits in either list OR a carry remains
        while l1 is not None or l2 is not None or carry != 0:
            # 5. Get current digits (or 0 if list is exhausted)
            val1 = l1.val if l1 is not None else 0
            val2 = l2.val if l2 is not None else 0

            # 6. Calculate the total sum for the current position
            total_sum = val1 + val2 + carry

            # 7. Determine the digit for the current node and the new carry
            new_digit = total_sum % 10
            carry = total_sum // 10

            # 8. Create a new node and append it to our result list
            current.next = ListNode(new_digit)
            # Move the 'current' pointer forward
            current = current.next

            # 9. Advance input list pointers if they exist
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next

        # 10. Return the actual head of the sum list (skipping the dummy_head)
        return dummy_head.next

Time & Space Complexity Analysis ⏱️📏

Understanding how much time and memory your solution uses is crucial for competitive programming!

Time Complexity: O(max(N, M))
- Where N is the number of nodes in l1 and M is the number of nodes in l2.
- We iterate through both linked lists at most once. The loop continues for a number of iterations equal to the length of the longer list, plus potentially one more if there's a final carry. Hence, the time taken scales linearly with the length of the longer input list.
Space Complexity: O(max(N, M))
- We create a new linked list to store the sum. In the worst case (e.g., adding two numbers like [9,9,9] and [1]), the result list can be one node longer than the longer input list ([0,0,0,1]).
- Therefore, the space used to store the result scales linearly with the length of the longer input list.

Key Takeaways ✨

Simulate Manual Processes: Many problems, especially arithmetic ones, can be solved by translating your "pen-and-paper" method into code.
The Power of a Dummy Node: A dummy head node is a fantastic pattern for simplifying linked list operations, especially when you're building a new list or might need to modify the original head. It avoids annoying edge cases where you'd have to handle the first node creation separately.
Handling Carries and Unequal Lengths: This problem is a great example of how to manage state (the carry) between iterations and gracefully handle inputs of different sizes.
Linked Lists for Big Numbers: Linked lists are often used in computer science to represent numbers of arbitrary length, exceeding what standard integer types can hold.

Congratulations! You've just walked through a fundamental LeetCode problem, learned about linked lists, and developed a solid approach. Keep practicing, and you'll be crushing those interviews in no time!

Authored by p1Hzd8mRM8. Published on 2026-05-16 22:58:14.

LeetCode Solution: 2. Add Two Numbers

Hommies — Sat, 16 May 2026 16:58:02 +0000

Unleash Your Inner Mathematician: Adding Numbers with Linked Lists (LeetCode #2)

Hey awesome developers! 👋 Ever wondered how computers perform basic arithmetic with a twist? Today, we're diving into a classic LeetCode problem that might seem simple on the surface but introduces some fundamental data structures and algorithmic thinking: "Add Two Numbers".

This problem is a fantastic way to sharpen your skills with linked lists and understand how to simulate everyday operations like addition programmatically. Don't worry if linked lists sound intimidating; we'll break it down piece by piece!

📚 Problem Explanation: Digits in Reverse!

Imagine you have two numbers, but instead of seeing them as regular integers like 342 or 465, their digits are stored in a special way: a linked list, and in reverse order!

Each "node" in our linked list holds a single digit. For example:

The number 342 would be represented as a linked list: 2 -> 4 -> 3
The number 465 would be: 5 -> 6 -> 4

Our mission? To add these two numbers together, digit by digit, and return their sum as another linked list, also in reverse order.

Let's look at Example 1:

Input: l1 = [2,4,3] (represents 342)
Input: l2 = [5,6,4] (represents 465)
Output: [7,0,8] (represents 807)

See? 342 + 465 = 807. The [7,0,8] linked list correctly gives us 807 in reverse!

A few important rules:

The lists are non-empty.
Digits are non-negative (0-9).
No leading zeros (unless the number itself is 0, like [0]).

🤔 Intuition: How Do We Add Numbers By Hand?

Before we jump into code, let's think about how you add numbers manually:

  342
+ 465
-----

Start from the rightmost digits: 2 + 5 = 7. Write down 7.
Move to the next digits (tens place): 4 + 6 = 10. Write down 0, and carry over 1 to the hundreds place.
Move to the next digits (hundreds place): 3 + 4 + (the carried-over 1) = 8. Write down 8.

The result is 807.

This "digit-by-digit, with a carry-over" strategy is exactly what we'll replicate with our linked lists! Since the digits are already in reverse order, it's like we're already starting from the rightmost digit (the units place)! This is a huge hint.

🪜 Approach: Step-by-Step with Linked Lists

Our approach will mimic manual addition:

Initialize:
- Create a dummy node. This is a common trick in linked list problems. It acts as a placeholder for the head of our new list. We'll eventually return dummy.next.
- Create a current pointer, initialized to dummy. This pointer will help us build our result list by moving forward.
- Initialize a carry variable to 0. This will store any carry-over from the previous sum.
Iterate through the lists: We need to keep adding digits as long as there are digits in either l1 or l2, or if there's still a carry left over from a previous addition. This while loop condition is crucial: while l1 or l2 or carry:
Calculate the sum for the current position:
- Start total_sum with the carry from the previous step.
- If l1 is not None (meaning there's a digit in the first number), add l1.val to total_sum and move l1 to its next node (l1 = l1.next).
- If l2 is not None (meaning there's a digit in the second number), add l2.val to total_sum and move l2 to its next node (l2 = l2.next).
Determine the current digit and new carry:
- The digit for our result list at the current position will be total_sum % 10 (the remainder after dividing by 10).
- The new carry will be total_sum // 10 (the integer division by 10).
Build the result list:
- Create a new ListNode with the calculated digit.
- Append this new node to our result list: current.next = new_node.
- Move current forward to this new node: current = current.next.
Return: Once the loop finishes, we've built our entire sum list. Return dummy.next to get the actual head of the sum list (skipping the initial placeholder dummy node).

This process continues until both input lists are exhausted AND there's no carry left.

💻 Code: Bringing It to Life (Python)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node to simplify handling the head of the result list
        dummy_head = ListNode()
        # 'current' pointer will build our new linked list
        current = dummy_head

        # Initialize carry to 0
        carry = 0

        # Loop as long as there are digits in either list or a carry exists
        while l1 or l2 or carry:
            # Get the value from l1 (or 0 if l1 is exhausted)
            val1 = l1.val if l1 else 0
            # Get the value from l2 (or 0 if l2 is exhausted)
            val2 = l2.val if l2 else 0

            # Calculate the total sum for the current position
            total_sum = val1 + val2 + carry

            # Determine the digit for the new node (units place of total_sum)
            digit = total_sum % 10
            # Determine the new carry (tens place of total_sum)
            carry = total_sum // 10

            # Create a new node with the calculated digit
            current.next = ListNode(digit)
            # Move our 'current' pointer forward to the new node
            current = current.next

            # Move l1 and l2 pointers forward if they are not exhausted
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        # The first node (dummy_head) was just a placeholder.
        # The actual result list starts from dummy_head.next.
        return dummy_head.next

⏱️ Time & Space Complexity Analysis

Time Complexity: O(max(m, n))

m is the number of nodes in l1.
n is the number of nodes in l2.
We iterate through both linked lists exactly once. The loop runs for a number of times proportional to the length of the longer list. This makes the time complexity linear with respect to the length of the longer input list.

Space Complexity: O(max(m, n))

In the worst-case scenario, the resulting linked list can have max(m, n) + 1 nodes (if there's a final carry-over). We are creating a new linked list to store the sum. Therefore, the space complexity is also linear with respect to the length of the longer input list.

🌟 Key Takeaways

Linked Lists for Arithmetic: This problem beautifully demonstrates how linked lists can be used to represent and manipulate numbers, especially useful when dealing with very large numbers that might exceed standard integer types.
The "Dummy Node" Trick: Using a dummy_head node is a super common and effective pattern in linked list problems. It simplifies code by always having a node to attach to, eliminating special checks for an empty result list or when adding the very first node.
Carry Handling: Understanding how to manage the carry digit is fundamental to correctly implementing addition, whether manually or programmatically.
Simulating Manual Processes: Many algorithmic problems can be solved by breaking them down into steps that mimic how we would solve them in real life.

This problem is a fantastic stepping stone for more complex linked list manipulations and numerical algorithms. Keep practicing, and you'll be a LeetCode master in no time! Happy coding!

Submission Details:
Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 22:27:48

LeetCode Solution: 1. Two Sum

Hommies — Sat, 16 May 2026 16:56:40 +0000

The OG LeetCode Challenge: Cracking Two Sum with Python!

Hey there, future coding rockstars! 👋

Ever wondered what the very first problem on LeetCode is? It's a true classic, a rite of passage for many, and a fantastic way to introduce fundamental data structures and algorithms. Today, we're diving into Two Sum! Don't let the "easy" tag fool you; mastering this problem helps build crucial problem-solving muscles.

Let's break it down together!

🧐 What's the Problem All About? (Problem Explanation)

Imagine you're given a list of numbers, like [2, 7, 11, 15], and a specific target number, say 9. Your mission, should you choose to accept it, is to find two different numbers in that list that add up to your target.

Once you find them, you don't return the numbers themselves, but their positions (their "indices") in the original list.

Example Time!

Input: nums = [2, 7, 11, 15], target = 9
Think: Can we find two numbers that sum to 9?
- 2 + 7 = 9! Bingo!
Output: [0, 1] (Because 2 is at index 0, and 7 is at index 1)

Another Example:

Input: nums = [3, 2, 4], target = 6
Think:
- 3 + 2 = 5 (Nope)
- 3 + 4 = 7 (Nope)
- 2 + 4 = 6! Yes!
Output: [1, 2] (2 is at index 1, 4 is at index 2)

Key things to remember:

You'll always find exactly one solution.
You can't use the same number twice (e.g., if nums had 3 and target was 6, you couldn't use the same 3 to make 3+3). If there are two 3s, you use both distinct 3s.

🤔 Your "Aha!" Moment (Intuition)

How would you solve this as a human, without a computer?

You might pick the first number (2 from [2, 7, 11, 15]), then look at every other number to see if it adds up to 9.

2 + 7 = 9 (Found it!)
If not, you'd try 2 + 11, 2 + 15.
If 2 didn't work with any other number, you'd move to the next number (7) and repeat the process.

This is what we call a brute-force approach. It works, but it can be slow for very long lists. For every number, you're looking at almost all other numbers. If there are N numbers, you might do N * N (or N^2) checks in the worst case. Can we do better?

The Smarter Way: What are we really looking for?

Let's say we pick a number from our list, nums[i]. We know we need another number, let's call it complement, such that:

nums[i] + complement = target

This means complement = target - nums[i].

So, for each nums[i] we encounter, we don't need to try every other number. We just need to quickly check if its specific complement exists somewhere else in our list.

How do we check for existence super fast? With a hash map (or a dictionary in Python)! A hash map allows us to store key-value pairs and look up keys almost instantly.

🚀 The Game Plan (Approach)

We'll use a two-pass hash map approach. This means we'll go through our nums list twice.

First Pass: Build the Lookup Table
- We'll create an empty hashmap (a Python dictionary).
- We iterate through nums one time. For each number nums[i] we see, we'll store it in our hashmap along with its index i.
- So, our hashmap will look something like {number: index}.
  - Example nums = [2, 7, 11, 15]:
    - After this pass, hashmap might be: {2: 0, 7: 1, 11: 2, 15: 3}.
Second Pass: Find the Complement
- Now, we iterate through nums again.
- For each number nums[i]:
  - Calculate its complement: complement = target - nums[i].
  - Check if this complement exists as a key in our hashmap.
  - Crucially, we also need to make sure that the index associated with the complement in the hashmap is not the current index i. This prevents us from trying to use the same number twice.
  - If both conditions are met (complement found, and it's a different number), we've found our pair! Return [i, hashmap[complement]].

Because the problem guarantees exactly one solution, we know we'll find our answer and return from the function during this second pass.

💻 Let's Code!

Here's the Python solution implementing the two-pass hash map approach:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Step 1: Initialize a hash map (Python dictionary) to store numbers and their indices
        hashmap = {} 

        # First Pass: Populate the hash map
        # We iterate through the array once to store each number and its index.
        # This makes subsequent lookups much faster.
        for i in range(len(nums)):
            hashmap[nums[i]] = i # Store: {number: index}

        # Second Pass: Find the complement
        # Now, we iterate through the array again. For each number, we calculate
        # what its 'complement' should be to reach the target.
        for i in range(len(nums)):
            complement = target - nums[i]

            # Check if the complement exists in our hash map:
            # - `complement in hashmap`: Is the required complement present in our stored numbers?
            # - `hashmap[complement] != i`: Is the complement not the current number itself (i.e., are their indices different)?
            #   This is important because we can't use the same element twice.
            if complement in hashmap and hashmap[complement] != i:
                # If both conditions are true, we found our pair!
                # Return the index of the current number (i) and the index of its complement.
                return [i, hashmap[complement]]

        # This line should ideally not be reached based on the problem constraints
        # (which state that exactly one solution exists).
        return []

⏰ Space and Time Efficiency (Complexity Analysis)

Understanding how efficient your code is, especially for large inputs, is a core skill!

Time Complexity: O(n)
- The first loop (for i in range(len(nums))) iterates n times to populate the hash map. On average, inserting an element into a hash map takes O(1) time. So, the first pass is O(n).
- The second loop (for i in range(len(nums))) also iterates n times. Inside this loop, calculating the complement is O(1), and looking up an element in a hash map takes O(1) time on average. So, the second pass is also O(n).
- Adding them up, O(n) + O(n) = O(2n), which simplifies to O(n). This is much faster than the O(n^2) brute-force approach!
Space Complexity: O(n)
- In the worst-case scenario, we might have to store all n numbers and their indices in our hashmap. Therefore, the space required grows linearly with the number of elements in the input array.

💡 Key Takeaways

Hash Maps are Your Friends: For problems involving quick lookups or checking for the existence of elements, hash maps (dictionaries) are incredibly powerful. They can transform a slow O(n) lookup into an average O(1) operation!
Think Complements: Many problems can be simplified by rephrasing what you're looking for. Instead of "find two numbers that sum to X", think "for each number, find its 'complement' (X - number)".
Optimize Iterations: While a brute-force approach (nested loops, O(n^2)) might be your first thought, always consider if you can reduce the number of passes or operations using a suitable data structure.

This problem, despite being "easy," introduces you to a fundamental pattern used in many more complex LeetCode challenges. Keep practicing, and you'll be solving harder problems in no time!

Happy coding! ✨

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-16 22:26:22