Longest Substring Without Repeating Characters

class Solution {
public:
    int maxUniqueSubstrLength(string str) {
        int length = int(str.length()), maxLen = 0;
        unordered_map<char, int> indexMap;

        for (int end = 0, start = 0; end < length; end++) {
            if (indexMap[str[end]] > 0) {
                start = max(indexMap[str[end]], start);
            }
            maxLen = max(maxLen, end - start + 1);
            indexMap[str[end]] = end + 1;
        }
        return maxLen;
    }
};

The provided C++ code defines a function to determine the length of the longest substring without repeating characters in a given string. Below is an overview of how this implemented function works:

• Initialize two integers for tracking the longest length and the current window of the non-repeating substring (maxLen and start respectively) and an unordered map (indexMap) for storing the character's last known index.
• Loop through the string using a for loop, with the variable end serving as the ending index pointer for your current substring under evaluation.
• Within the loop, check if the current character is already in the map and adjust the starting index (start) accordingly, ensuring no repeated characters are in the current substring by moving the start index past the last occurrence of the current character.
• The loop also calculates the maximum length so far by comparing the current substring length (from start to end) with the previously found maximum lengths.
• Each character and its index (incremented by one) are stored in the indexMap. This allows you to maintain an updated index for each character that adjusts the start when a repeat character is found.
• The function concludes by returning maxLen, which contains the length of the longest substring without repeating characters discovered through this process.

This function provides an efficient solution using a sliding window technique combined with hash mapping, ensuring a time complexity close to O(n), where n is the number of characters in the string. This efficiency comes from the fact that each index is processed only once with constant-time operations due to unordered_map.

public class Solution {
    public int findMaxLengthSubstring(String str) {
        int length = str.length(), maxLen = 0;
        Map<Character, Integer> indexMap = new HashMap<>();
        for (int end = 0, start = 0; end < length; end++) {
            if (indexMap.containsKey(str.charAt(end))) {
                start = Math.max(indexMap.get(str.charAt(end)), start);
            }
            maxLen = Math.max(maxLen, end - start + 1);
            indexMap.put(str.charAt(end), end + 1);
        }
        return maxLen;
    }
}

The provided Java solution efficiently tackles the problem of finding the longest substring without repeating characters in a given string. The solution uses a sliding window algorithm represented by two pointers, start and end, and a hash map indexMap that keeps track of the characters and their latest indices in the string.

Here's a concise breakdown of how the solution operates:

• Initialize maxLen to zero to store the maximum length of substring found and indexMap to store characters and their indices.
• Iterate through the string with the end pointer:
  • Check if the current character at the end pointer exists in the indexMap.
  • If it exists and the stored index is greater than or equal to start, update start to the maximum value between the current start and the character's last index from indexMap to avoid including repeated characters.
  • Calculate the length of the current substring by end - start + 1 and update maxLen if it's the longest found so far.
  • Update indexMap with the current character and its index +1.
• Return maxLen which contains the length of the longest substring without repeating characters.

This approach ensures that each character in the string is processed once, leading to a time complexity of O(n), where n is the length of the string. The space complexity is O(min(m, n)) where m is the size of the character set. With these mechanics, the algorithm balances efficiency and clarity, making it effective for strings of considerable length.

int substringUniqueLength(char* s) {
    int lastPos[256] = {0};  // Array for mapping character to last position
    int longest = 0;
    int start = 0;
    int strLen = strlen(s);
    for (int end = 0; end < strLen; end++) {
        int character = (int)s[end];
        if (lastPos[character] > 0) {
            start = max(start, lastPos[character]);
        }
        longest = max(longest, end - start + 1);
        lastPos[character] = end + 1;
    }
    return longest;
}

int max(int x, int y) { return (x > y) ? x : y; }

This program, written in C, computes the length of the longest substring without repeating characters from a given string. The function substringUniqueLength uses an integer array lastPos to track the last position of each character within the ASCII range. Here is how it achieves this:

1. Initialize an array lastPos of size 256 to store the last positions of characters, initially filled with zeros.
2. Define variables longest to keep track of the maximum length of substring found, and start to mark the beginning of a possible substring.
3. Execute a loop from start to the end of the string. For each character:
   • Convert the character s[end] to its ASCII equivalent character.
   • If the character was seen before and is within the current substring, update the start to the maximum of start and last seen position of the character.
   • Calculate the potential longest substring from the current start to end and compare it with the longest found so far.
   • Update the last seen position of the current character.
4. Return the length of the longest substring found.

The helper function max is used to determine the greater of two numbers, simplifying the process of updating lengths and starting positions. This approach ensures that each character's position is updated only while it is part of the current substring, optimizing the search for the longest possible substring without duplicates.

var longestSubstringWithoutRepeating = function (str) {
    let indexMap = new Map();
    let maxLength = 0;
    let start = 0;
    for (let end = 0; end < str.length; end++) {
        if (indexMap.has(str[end])) {
            start = Math.max(indexMap.get(str[end]), start);
        }
        maxLength = Math.max(maxLength, end - start + 1);
        indexMap.set(str[end], end + 1);
    }
    return maxLength;
};

The solution provided is a JavaScript function designed to determine the length of the longest substring without repeating characters in a given string. It efficiently handles this task by using a sliding window technique combined with a Map to track the most recent index of each character.

• Inside the function longestSubstringWithoutRepeating, two main variables are initialized: indexMap for storing character indices, and maxLength to keep track of the maximum length of substring found.
• The loop runs through each character in the string. Inside the loop:
  • Check if the character already has a recorded index greater than the current start position. If so, update start to the recorded index to ensure the window only contains unique characters.
  • Update maxLength to store the size of the current window if it is the largest found so far.
  • Record the index of the current character in the map.
• After processing all characters, maxLength will contain the length of the longest substring without repeating characters, and the function returns this value.

This approach ensures efficient computation, updating the necessary variables to maintain non-repeated characters within a dynamically resizing window, leveraging the random-access capabilities of the JavaScript Map to immediately locate indices of characters.

class Solution:
    def findMaxNonRepeatingSubstrLen(self, input_string: str) -> int:
        string_length = len(input_string)
        max_length = 0
        index_map = {}

        start_index = 0
        for end_index in range(string_length):
            if input_string[end_index] in index_map:
                start_index = max(index_map[input_string[end_index]], start_index)

            max_length = max(max_length, end_index - start_index + 1)
            index_map[input_string[end_index]] = end_index + 1

        return max_length

The Python solution provided calculates the length of the longest substring without repeating characters in a given string using a sliding window technique and a hash map. The method findMaxNonRepeatingSubstrLen accepts a string and processes it to determine the longest unique substring. Below outlines how the solution operates:

1. Initialize string_length to hold the length of the input string.
2. max_length is used to track the length of the longest non-repeating substring found so far.
3. index_map maps characters to their latest index plus one in the string.
4. start_index is used to maintain the starting index of the current window of characters that are being considered.

As you iterate over each character (end_index as the current position):

• Update start_index to either its current value or the value indexed in index_map for the current character, depending on which is greater. This helps in adjusting the window size whenever a repeating character is found.
• Update max_length to be the maximum value between itself and the length of the current window (end_index - start_index + 1).
• Store or update in index_map the next index for the current character (end_index + 1).

The method concludes by returning max_length, which at the end of the loop will contain the length of the longest substring without repeating characters. This approach efficiently solves the problem with a time complexity of O(n), where n is the length of the string, using a single pass through the string and constant space relative to the character set size.