DEV Community

Cover image for 3. Longest Substring Without Repeating Characters
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

1

3. Longest Substring Without Repeating Characters

3. 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.

Example 3:

  • Input: s = "pwwkew"
  • Output: 3
  • Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

  • Input: s = ""
  • Output: 0

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Hint:

  1. Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly.

Solution:

To solve this problem, we can follow these steps:

  1. Initialize Variables:

    • maxLength to store the maximum length of substring found.
    • charIndexMap to store the last index of each character encountered.
    • start to represent the starting index of the current window.
  2. Sliding Window:

    • Iterate through the string with an index end representing the end of the current window.
    • If the character at s[end] is already in the charIndexMap and its index is greater than or equal to start, move the start to charIndexMap[s[end]] + 1.
    • Update the charIndexMap with the current index of s[end].
    • Calculate the current window length (end - start + 1) and update maxLength if it's larger than the previously recorded maximum length.

Let's implement this solution in PHP: 3. Longest Substring Without Repeating Characters

<?php
// Example usage:
echo lengthOfLongestSubstring("abcabcbb") . "\n"; // Output: 3
echo lengthOfLongestSubstring("bbbbb") . "\n";    // Output: 1
echo lengthOfLongestSubstring("pwwkew") . "\n";   // Output: 3
echo lengthOfLongestSubstring("") . "\n";         // Output: 0

?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Initialization:

    • $maxLength is set to 0 to store the length of the longest substring without repeating characters.
    • $charIndexMap is an associative array to keep track of the last index at which each character was seen.
    • $start is initialized to 0 to represent the start of the current substring.
  2. Iterating through the String:

    • Loop through each character of the string with the index $end.
    • Check if the character is already in $charIndexMap and its recorded index is within the current substring (i.e., >= $start).
    • If so, move the start to charIndexMap[$char] + 1 to ensure no duplicates in the current window.
    • Update $charIndexMap[$char] to the current index $end.
    • Calculate the length of the current substring and update $maxLength if this length is greater than the previously recorded maximum length.
  3. Return Result:

    • Finally, return $maxLength which holds the length of the longest substring without repeating characters.

This solution efficiently finds the desired substring length with a time complexity of O(n), where n is the length of the input string.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay