Longest Substring Without Repeating Characters

                                            
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i < s.size(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }
};

                                            
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
            if (map.containsKey(s.charAt(i))) {
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}

                                            
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        chars = {}
        left = 0
        right = 0
        max_len = 0
        while right < len(s):
            if s[right] in chars and chars[s[right]] >= left:
                left = chars[s[right]] + 1
            max_len = max(max_len, right - left + 1)
            chars[s[right]] = right
            right += 1
        return max_len

                                            
int lengthOfLongestSubstring(char* s) {
    int max_length = 0, start = 0;
    int char_index[256];   // ASCII table size
    for (int i = 0; i < 256; i++) {
        char_index[i] = -1;
    }

    for (int i = 0; s[i] != '\0'; i++) {
        if (char_index[(unsigned char)s[i]] >= start) {
            start = char_index[(unsigned char)s[i]] + 1;
        }
        char_index[(unsigned char)s[i]] = i;
        max_length = max_length > (i - start + 1) ? max_length : (i - start + 1);
    }

    return max_length;
}

                                            
public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int n = s.Length;
        int i = 0, j = 0, maxLength = 0;
        HashSet<char> set = new HashSet<char>();

        while (j < n) {
            if (!set.Contains(s[j])) {
                set.Add(s[j++]);
                maxLength = Math.Max(maxLength, set.Count);
            } else {
                set.Remove(s[i++]);
            }
        }
        return maxLength;
    }
}

                                            
var lengthOfLongestSubstring = function(s) {
    let map = {};
    let start = 0;
    let maxLength = 0;
    
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (map[char] >= start) {
            start = map[char] + 1;
        }
        map[char] = i;
        maxLength = Math.max(maxLength, i - start + 1);
    }
    
    return maxLength;
};

                                            
function lengthOfLongestSubstring(s: string): number {
    let map = new Map<string, number>();
    let left = 0;
    let maxLen = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        if (map.has(char)) {
            left = Math.max(map.get(char)! + 1, left);
        }
        map.set(char, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

                                            
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $n = strlen($s);
        $maxLen = 0;
        $map = [];
        $left = 0;

        for ($right = 0; $right < $n; $right++) {
            $char = $s[$right];
            if (array_key_exists($char, $map)) {
                $left = max($map[$char] + 1, $left);
            }
            $map[$char] = $right;
            $maxLen = max($maxLen, $right - $left + 1);
        }

        return $maxLen;
    }
}

                                            
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var charSet = Set<Character>()
        var left = 0
        var maxLength = 0
        
        let chars = Array(s)
        
        for (i, char) in chars.enumerated() {
            while charSet.contains(char) {
                charSet.remove(chars[left])
                left += 1
            }
            charSet.insert(char)
            maxLength = max(maxLength, i - left + 1)
        }
        
        return maxLength
    }
}

                                            
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val n = s.length
        var longest = 0
        var start = 0
        val map = mutableMapOf<Char, Int>()

        for (end in 0 until n) {
            if (s[end] in map) {
                start = maxOf(map[s[end]]!! + 1, start)
            }
            map[s[end]] = end
            longest = maxOf(longest, end - start + 1)
        }
        return longest
    }
}

                                            
class Solution {
  int lengthOfLongestSubstring(String s) {
    Map<String, int> map = {};
    int start = 0, maxLength = 0;

    for (int i = 0; i < s.length; i++) {
      String c = s[i];
      if (map.containsKey(c)) {
        start = max(start, map[c]! + 1);
      }
      map[c] = i;
      maxLength = max(maxLength, i - start + 1);
    }
    return maxLength;
  }
}

                                            
func lengthOfLongestSubstring(s string) int {
    charMap := make(map[byte]int)
    maxLength := 0
    l := 0
    
    for r := 0; r < len(s); r++ {
        if index, found := charMap[s[r]]; found && index >= l {
            l = index + 1
        }
        charMap[s[r]] = r
        if maxLength < r-l+1 {
            maxLength = r-l+1
        }
    }
    
    return maxLength
}

                                            
def length_of_longest_substring(s)
  chars = {}
  max_length = 0
  left = 0

  s.chars.each_with_index do |char, right|
    if chars.include?(char) && chars[char] >= left
      left = chars[char] + 1
    end

    chars[char] = right
    max_length = [max_length, right - left + 1].max
  end

  max_length
end

                                            
object Solution {
    def lengthOfLongestSubstring(s: String): Int = {
        var maxLen = 0
        var start = 0
        val map = scala.collection.mutable.Map[Char, Int]()

        for (end <- 0 until s.length) {
            val ch = s(end)
            if (map.contains(ch)) {
                start = math.max(start, map(ch) + 1)
            }
            map(ch) = end
            maxLen = math.max(maxLen, end - start + 1)
        }
        maxLen
    }
}

                                            
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        use std::collections::HashMap;
        let (mut max_len, mut start) = (0, 0);
        let mut last_seen = HashMap::new();

        for (i, c) in s.chars().enumerate() {
            if let Some(prev) = last_seen.get(&c) {
                start = start.max(prev + 1);
            }
            max_len = max_len.max(i + 1 - start);
            last_seen.insert(c, i);
        }

        max_len as i32
    }
}

                                            
-spec length_of_longest_substring(S :: unicode:unicode_binary()) -> integer().
length_of_longest_substring(S) ->
    length_of_longest_substring(S, maps:new(), 0, 0, 0).

length_of_longest_substring(<<>>, _CharMap, MaxLen, _, _) ->
    MaxLen;
length_of_longest_substring(<<H, Rest/binary>>, CharMap, MaxLen, L, R) ->
    {NewL, UpdatedCharMap} =
        case maps:find(H, CharMap) of
            {ok, PrevIndex} when PrevIndex >= L ->
                {PrevIndex + 1, maps:put(H, R, CharMap)};
            _ ->
                {L, maps:put(H, R, CharMap)}
        end,
    NewMaxLen = max(MaxLen, R - NewL + 1),
    length_of_longest_substring(Rest, UpdatedCharMap, NewMaxLen, NewL, R + 1).

                                            
defmodule Solution do
  def length_of_longest_substring(s) do
    longest_substring(s, %{}, 0, 0, 0)
  end

  defp longest_substring("", _seen, max_len, _start, _idx),
    do: max_len

  defp longest_substring(<<h::utf8, rest::binary>>, seen, max_len, start, idx) do
    ch = <<h::utf8>>
    case Map.get(seen, ch) do
      nil ->
        longest_substring(rest, Map.put(seen, ch, idx), max(max_len, idx - start + 1), start, idx + 1)

      pos when pos >= start ->
        longest_substring(rest, Map.put(seen, ch, idx), max_len, pos + 1, idx + 1)

      _ ->
        longest_substring(rest, Map.put(seen, ch, idx), max(max_len, idx - start + 1), start, idx + 1)
    end
  end
end

To solve this coding challenge of finding the longest substring without repeating characters, we can use a sliding window approach. This challenge can be efficiently solved by using two pointers and a hash map (or dictionary) to keep track of the characters and their positions.

Explanation

In this problem, we need to identify the longest substring within a given string

s

that does not contain any repeating characters. A sliding window is an effective method to achieve this, where we use two pointers (

left

and

right

) to represent the current window of characters being considered. By using a hash map, we store the most recent index of each character. Here is a step-by-step method to solve the challenge:

Initialize two pointers:

left

(beginning of the current window)
right

(end of the current window)

Initialize a dictionary (
char_position

) to store the most recent index of each character within the current window.
Initialize a variable (
max_length

) to track the length of the longest substring without repeating characters.
Iterate through the string using the
right

pointer:

If the current character exists in the dictionary and its stored index is within the current window, move the
left

pointer just after the previous occurrence of the current character to ensure no duplicates within the window.
Update the length of the longest substring, if the current window is larger.
Update the dictionary with the current character's position.

Return the longest length found.

With this understanding, we can transform the steps into the following pseudocode:

Detailed Steps in Pseudocode

                                            
# Initialize the necessary variables
Initialize char_position as an empty dictionary  # To store the last occurrence of characters
Initialize left as 0  # Starting index of the window
Initialize max_length as 0  # Maximum length of substring without repeating characters

# Iterate over the string with the end index representing the current character
For right from 0 to the length of the string (s):
    # If the current character is already in the dictionary and is within the current window
    If s[right] is in char_position and char_position[s[right]] >= left:
        # Move the left pointer to the right of the last occurrence of the current character
        left = char_position[s[right]] + 1

    # Calculate the window size and update the maximum length if necessary
    max_length = max(max_length, right - left + 1)
    
    # Update the current character's position in the dictionary
    char_position[s[right]] = right

# Return the maximum length of the substring found
Return max_length

Explanation of Key Points

Initializing Dictionary : The dictionary is used to track the most recent positions where characters appeared.
Updating Left Pointer : If a character repeats itself and is within the current window, the left pointer is moved just after its previous index to ensure that the substring within the window remains distinct.
Updating Maximum Length : On every iteration, the size of the current window is checked and the maximum length is updated accordingly.
Final Return : After looping through the string, the variable
max_length

holds the length of the longest substring without repeating characters.

This approach ensures that each character in the string is processed efficiently, leading to an average time complexity of O(n). This methodology incorporates key techniques like sliding windows and hash map usage, making it not just effective but also educational in understanding common patterns for similar problems.