Longest unique substring

 

Test Case 1

In the brute-force approach to generating substrings using nested loops, maintaining a hashmap that counts each character's occurrence as 1 (e.g., setting counts to 1 regardless of actual frequency) is invalid. Proper substring generation and validation require accurately tracking character counts in the hashmap rather than assuming all characters occur only once.

geekforgeeks
eekforgeeks
ekforgeeks
kforgeeks
forgeeks
orgeeks
rgeeks
geeks
eeks
eks
ks
s

Test Case 2

From the following output, what we actually need is a contiguous substring of characters that satisfies our problem constraints. For example, in the second case, the longest substring without repeating characters is 'ksforg' or 'stoare'—these substrings are contiguous and contain no repeating characters.

geekforgeeks
eekforgeek
ekforgee
kforge
forg
or
o

Test Case 3

We can use a fixed-size sliding window to find substrings. Starting with a window of fixed size, we keep decreasing the window size until we find a substring with the longest length where all characters are non-repeating. This approach aims to find the longest substring without repeating characters. Alternatively, we can use a brute-force approach on the string to find such substrings.

Python Code

def is_non_repeated(str2):
    n=len(str2)
    a=dict()
    for i in str2:
        a[i]=str2.count(i)
    for j in a.values():
        if j!=1:
            return False
    return True

def generate_fixed_substring(w,str1):
    l=[]
    for i in range(0,len(str1)-w+1):
        substr=str1[i:i+w]
        l.append(substr)
    return l

def main():
    str1="geeksforgeeks"
    w=len(str1)
    found=False
    while w!=1:
        
        for i in generate_fixed_substring(w,str1):
            if is_non_repeated(i):
                print(i)
                found=True
                break
        if found==True:
            break
        w-=1
            
if __name__=="__main__":
    main()

Longest Substring Without Repeating Characters - C++

Longest Substring Without Repeating Characters (C++)

// Function to find length of longest substring without repeating characters
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

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

    for (int end = 0; end < s.length(); end++) {
        char currentChar = s[end];
        if (charIndex.find(currentChar) != charIndex.end() && charIndex[currentChar] >= start) {
            start = charIndex[currentChar] + 1;
        }
        charIndex[currentChar] = end;
        maxLength = max(maxLength, end - start + 1);
    }
    return maxLength;
}

int main() {
    string input = "abcabcbb";
    cout << "Length of longest substring without repeating characters: " << lengthOfLongestSubstring(input) << endl;
    return 0;
}

Java

import java.util.HashMap;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        HashMap charIndexMap = new HashMap<>();
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);
            if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= start) {
                start = charIndexMap.get(currentChar) + 1;
            }
            charIndexMap.put(currentChar, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String input = "abcabcbb";
        int result = lengthOfLongestSubstring(input);
        System.out.println("Length of longest substring without repeating characters: " + result);
    }
}

Rust

use std::collections::HashMap;

fn length_of_longest_substring(s: &str) -> usize {
    let mut char_index_map = HashMap::new();
    let mut max_length = 0;
    let mut start = 0;

    for (end, ch) in s.chars().enumerate() {
        if let Some(&prev_index) = char_index_map.get(&ch) {
            if prev_index >= start {
                start = prev_index + 1;
            }
        }
        char_index_map.insert(ch, end);
        max_length = max_length.max(end - start + 1);
    }

    max_length
}

fn main() {
    let input = "abcabcbb";
    let result = length_of_longest_substring(input);
    println!("Length of longest substring without repeating characters: {}", result);
}