LengthOfLongestSubstring

Problem

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Solution

The longest substring can start from any position in the string. So, we must iterate through each position in the entire string. For each position, we look right until we find a duplicate character. At each iteration, if the current substring is longer than the longest, we update the length of the longest substring. Once we find a duplicate character, reset the seen characters.

Code

https://github.com/GeorgeRPu/tech-interview-prep/blob/main/solutions/LengthOfLongestSubstring.py

"""


from typing import List


def maxProfit(prices: List[int]) -> int:
    """Find the maximum profit that can be made by buying and selling a stock
    once on different days.
    """
    max_profit = 0
    buy_price = float('inf')
    for price in prices:
        if price < buy_price:
            buy_price = price
        else:
            max_profit = max(price - buy_price, max_profit)
    return max_profit

Test

>>> from LengthOfLongestSubstring import lengthOfLongestSubstring
>>> lengthOfLongestSubstring('abcabcbb')
3
>>> lengthOfLongestSubstring('bbbbb')
1
>>> lengthOfLongestSubstring('pwwkew')
3

Functions

lengthOfLongestSubstring(s)

Finds the length of the longest substring without repeating characters.