Home Java javaTutorial Longest substring without repeating characters

Longest substring without repeating characters

Sep 24, 2024 am 06:21 AM

Longest substring without repeating characters

Problem

Brute force approach will involve creating all the possible substrings of the given string and finding out which one is the longest substring without the repeating character. This will lead to TC:O(n^2)

Optimal approach:
TC : O(n)
SC : O(256), for using int[] of size 256

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int hash[] = new int[256];// size of all the ascii characters
        Arrays.fill(hash,-1); // -1 to indicate these indexes don't have any character visited already
        int left =0,right =0;
        int max = 0;
        while(right<s.length()){
            char  c = s.charAt(right);
            if(hash[c]!=-1){// means the character has been seen in the past
                if(hash[c]>=left){// if the index of the character seen in the past is after the left pointer, then left pointer should be updated, to avoid duplicate in the window of substring
                    left  = hash[c] + 1;// has to be 1 index after the index of last seen duplicate character
                }
            }
            max = Integer.max(max, right-left+1);// keep track of mas window substring
            hash[c]  = right;// update the character last seen index in hash
            right++;
        }
        return max;
    }
}
Copy after login

The above is the detailed content of Longest substring without repeating characters. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Mar 07, 2025 pm 06:09 PM

Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte

How does Java's classloading mechanism work, including different classloaders and their delegation models? How does Java's classloading mechanism work, including different classloaders and their delegation models? Mar 17, 2025 pm 05:35 PM

How does Java's classloading mechanism work, including different classloaders and their delegation models?

How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution? How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution? Mar 17, 2025 pm 05:46 PM

How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?

Node.js 20: Key Performance Boosts and New Features Node.js 20: Key Performance Boosts and New Features Mar 07, 2025 pm 06:12 PM

Node.js 20: Key Performance Boosts and New Features

Iceberg: The Future of Data Lake Tables Iceberg: The Future of Data Lake Tables Mar 07, 2025 pm 06:31 PM

Iceberg: The Future of Data Lake Tables

How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache? How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache? Mar 17, 2025 pm 05:44 PM

How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?

Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Mar 07, 2025 pm 05:52 PM

Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed

How to Share Data Between Steps in Cucumber How to Share Data Between Steps in Cucumber Mar 07, 2025 pm 05:55 PM

How to Share Data Between Steps in Cucumber

See all articles