Skip to content

Instantly share code, notes, and snippets.

@ramonrails
Last active November 12, 2023 09:11
Show Gist options
  • Save ramonrails/213f688a53a7ca710b93da9a0f33c89f to your computer and use it in GitHub Desktop.
Save ramonrails/213f688a53a7ca710b93da9a0f33c89f to your computer and use it in GitHub Desktop.
Leetcode #3 (flawed?)
# [Leetcode #3](https://leetcode.com/problems/longest-substring-without-repeating-characters/) says
# 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.
#
# Why does it seem flawed?
# Problem statement says "Given a string s, find the length of the longest substring without repeating characters"
#
# Leetcode example 2
# "bbbbb" => "b" # should result in 1, because the first 'b' is non-repeating. The 2nd 'b' is repeating.
#
# Leetcode example 1 = flawed based on example 2
# "abcabcbb" => "abcabcb" # should result in 7, not 3, because (1) "abc" is repeating as a word, not character, so "abcabc" becomes non-repeating. (2) repeating "b" gets counted the first time as non-repeating at least. If "bbbbb" results in 1 by counting the first "b" as non-repeating, then why is it not counted in "abcabcb"?.
#
# Leetcode example 3 = flawed based on example 2
# "pwwkew" => "wkew" # should result in 4, not 3
#
# If example 1 and 3 are correct logic, then the result of example 2 should be ZERO
# The solution
#
# what is this "gsub(/(.)\1+/, '-\1')" regex logic/magic?
#
# (.) = any character, as a "match"
# \1 = first match
# + = one or more chars = also means entire "substring"
# -\1 = '-' as literal, \1 as first "match"
#
# @param {String} s
# @return {Integer}
def lls(s)
# generate a potential string for regex match
(
# replace repeating chars with '-' as prefix
s.gsub(/(.)\1+/, '-\1')
# just a separator
+' '+
# replace repeating chars with '-' as suffix
s.gsub(/(.)\1+/, '\1-')
)
# regex scan for words
.scan(/\w+/)
# collect all word-lengths
.collect(&:length)
# find the max length
.max
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment