Last active
November 12, 2023 09:11
-
-
Save ramonrails/213f688a53a7ca710b93da9a0f33c89f to your computer and use it in GitHub Desktop.
Leetcode #3 (flawed?)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# [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