🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Solution
  • Test Cases
  1. Problems
  2. LeetCode

3. Longest Substring Without Repeating Characters

Previous1. Two SumNext5. Longest Palindromic Substring

Last updated 3 years ago

See description at

Solution

Given an input string like "abcabcbb" we need to find the longest substring without repeating characters.

Two pointers are used to keep track of the start and end (left and right) of a substring. A cache is also used to store the seen characters. The left and right pointers are initially set to the first index in the array. The character at the right pointer is stored in the cache. The key is the character and the value is the index position. When a duplicate character is seen, then the left pointer is moved.

This is kind of a combination of the two solutions in the problem.

def lengthOfLongestSubstring(self, s: str) -> int:
    seen = defaultdict(int)
    left, right = 0, 0
    answer = 0
    while right < len(s) :
        if s[right] in seen:
            # need to take the max here because the left pointer may have moved past
            # the index where the letter was previously seen. case: "abba"
            left = max(left, seen[s[right]] + 1)
        answer = max(answer, right - left + 1)  
        seen[s[right]] = right
        right += 1
    return answer
        

Test Cases

input
output

"abcabcbb"

3

"bbbbb"

1

"pwwkew"

3

"ababab"

2

"a"

1

"ab"

2

"abbc"

2

"abbcbdefgh"

7

"abbcbdefghc"

7

" "

1

"a b%7c7"

6

""

0

"bb"

1

"abba"

2

"1212345"

5

3. Longest Substring Without Repeating Characters
Two Sum