3. Longest Substring Without Repeating Characters

 

Mastering the Longest Substring Without Repeating Characters Problem Using Sliding Window and Set

Introduction

Welcome to another deep dive into solving classic algorithm problems! Today, we’re tackling the Longest Substring Without Repeating Characters problem. This is a common problem that tests your understanding of data structures and algorithmic techniques. We’ll explore an efficient solution using the sliding window technique combined with a Set. This approach is both intuitive and powerful, enabling us to solve the problem efficiently.

Problem Description

Given a string s, find the length of the longest substring without repeating characters. Essentially, we need to find the maximum length of a substring where no characters repeat.

Intuition

To solve this problem, we need to maintain a window (substring) where all characters are unique. The sliding window technique allows us to dynamically adjust the size of this window and ensure it contains only unique characters. We use a Set to keep track of the characters in the current window efficiently.

Approach

  1. Initialize Variables:

    • result: Stores the length of the longest substring found so far.

    • left: Represents the starting index of the current window.

    • charSet: A Set to store characters in the current window, ensuring no duplicates.

  2. Expand the Window:

    • Iterate through the string with a for-loop.

    • For each character s[i], check if it's already in charSet.

    • If it is, remove characters from the left side of the window until s[i] can be added without duplicates.

  3. Update Results:

    • Add s[i] to charSet.

    • Update result to the maximum length found so far.

  4. Return Result:

    • Return result after processing the entire string.

Code Implementation

Here’s the JavaScript code that efficiently finds the length of the longest substring without repeating characters:

javascript
var lengthOfLongestSubstring = function(s) {
    let result = 0;
    let left = 0;
    let charSet = new Set();
    for(let i = 0; i < s.length; i++) {
        while(charSet.has(s[i])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[i]);
        result = Math.max(result, i - left + 1);
    }
    return result;
};

Highlight: Sliding Window Technique

The sliding window technique is a powerful tool for solving problems involving contiguous segments of an array or string. By dynamically adjusting the window size, we can efficiently handle a wide range of problems.

In this problem, the sliding window technique allows us to maintain a window where all characters are unique. We expand the window by moving the right pointer (i), and contract it by moving the left pointer (left) when we encounter a duplicate character.

Highlight: Use of Set

The Set data structure is crucial in this solution. It allows us to efficiently check for duplicates and remove characters, ensuring the operations are performed in constant time on average.

  • Checking for Duplicates: Using the Set, we can quickly check if a character is already in the current window.

  • Removing Characters: The Set enables us to efficiently remove characters from the left side of the window when necessary.

Complexity Analysis

  • Time Complexity: The time complexity is O(n)O(n), where nn is the length of the string. Each character is processed at most twice, once when added and once when removed from the Set.

  • Space Complexity: The space complexity is O(min(n,m))O(min(n, m)), where mm is the size of the character set (e.g., 26 for lowercase letters), as the Set stores distinct characters in the window.

Conclusion

The sliding window technique, combined with a Set, provides an efficient and elegant solution to the Longest Substring Without Repeating Characters problem. By mastering this approach, you’ll be better equipped to tackle a variety of algorithmic challenges.

I hope you found this exploration insightful! If you have any questions or additional insights, feel free to share in the comments.

Happy coding! šŸ˜Š

LeetCode Solution Link : https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/6168369/solution-using-set-in-js-by-bikash_kumar-ukcf/

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more