Longest Substring Without Repeating Characters In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement

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

Constraints

1. 0 <= s.length <= 5 * 10^4
2. s consists of English letters, digits, symbols, and spaces.

Examples

• Input: "abcabcbb"
  • Output: 3 (Explanation: The answer is “abc” with length 3.)
• Input: "bbbbb"
  • Output: 1 (Explanation: The answer is “b” with length 1.)
• Input: "pwwkew"
  • Output: 3 (Explanation: The answer is “wke” with length 3.)

---

Approach

The problem can be solved efficiently using the Sliding Window Technique. Here’s how:

1. Use two pointers (start and end) to define a sliding window over the string.
2. Use a data structure (e.g., set or map) to store characters in the current window.
3. If a character is repeated, shrink the window from the left by moving the start pointer until the character is removed.
4. Track the maximum length of the substring during this process.

Algorithm

1. Initialize:
   • start = 0, max_len = 0
   • A map or set to store characters in the current window.
2. Iterate over the string using end pointer:
   • If s[end] is not in the set/map, add it and update max_len.
   • If it’s a duplicate, move the start pointer and remove characters until s[end] is unique.
3. Return max_len after processing the string.

---

Code Implementations

1. C

#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(char *s) {
    int n = strlen(s);
    int max_len = 0, start = 0;
    int map[128] = {0};

    for (int end = 0; end < n; end++) {
        if (map[s[end]] > 0) {
            start = (map[s[end]] > start) ? map[s[end]] : start;
        }
        map[s[end]] = end + 1;
        max_len = (max_len > end - start + 1) ? max_len : end - start + 1;
    }

    return max_len;
}

int main() {
    char str[] = "abcabcbb";
    printf("Length of Longest Substring: %d\n", lengthOfLongestSubstring(str));
    return 0;
}

---

2. C++

#include <iostream>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> map;
    int start = 0, max_len = 0;

    for (int end = 0; end < s.length(); end++) {
        if (map.find(s[end]) != map.end()) {
            start = max(map[s[end]] + 1, start);
        }
        map[s[end]] = end;
        max_len = max(max_len, end - start + 1);
    }

    return max_len;
}

int main() {
    string str = "abcabcbb";
    cout << "Length of Longest Substring: " << lengthOfLongestSubstring(str) << endl;
    return 0;
}

---

3. Java

import java.util.HashMap;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0, max_len = 0;

        for (int end = 0; end < s.length(); end++) {
            if (map.containsKey(s.charAt(end))) {
                start = Math.max(map.get(s.charAt(end)) + 1, start);
            }
            map.put(s.charAt(end), end);
            max_len = Math.max(max_len, end - start + 1);
        }

        return max_len;
    }

    public static void main(String[] args) {
        String str = "abcabcbb";
        System.out.println("Length of Longest Substring: " + lengthOfLongestSubstring(str));
    }
}

---

4. Python

def length_of_longest_substring(s: str) -> int:
    char_map = {}
    start, max_len = 0, 0

    for end, char in enumerate(s):
        if char in char_map and char_map[char] >= start:
            start = char_map[char] + 1
        char_map[char] = end
        max_len = max(max_len, end - start + 1)

    return max_len

# Example usage
print("Length of Longest Substring:", length_of_longest_substring("abcabcbb"))

---

5. C#

using System;
using System.Collections.Generic;

class LongestSubstring {
    public static int LengthOfLongestSubstring(string s) {
        Dictionary<char, int> map = new Dictionary<char, int>();
        int start = 0, max_len = 0;

        for (int end = 0; end < s.Length; end++) {
            if (map.ContainsKey(s[end]) && map[s[end]] >= start) {
                start = map[s[end]] + 1;
            }
            map[s[end]] = end;
            max_len = Math.Max(max_len, end - start + 1);
        }

        return max_len;
    }

    static void Main(string[] args) {
        string str = "abcabcbb";
        Console.WriteLine("Length of Longest Substring: " + LengthOfLongestSubstring(str));
    }
}

---

6. JavaScript

Copy codefunction lengthOfLongestSubstring(s) {
    let charMap = new Map();
    let start = 0, maxLen = 0;

    for (let end = 0; end < s.length; end++) {
        if (charMap.has(s[end]) && charMap.get(s[end]) >= start) {
            start = charMap.get(s[end]) + 1;
        }
        charMap.set(s[end], end);
        maxLen = Math.max(maxLen, end - start + 1);
    }

    return maxLen;
}

console.log("Length of Longest Substring:", lengthOfLongestSubstring("abcabcbb"));

---

Time Complexity

• The algorithm runs in O(n) time because each character is processed at most twice (once by end and possibly once by start).

Space Complexity

• O(n) for storing characters in the map or set.