Longest substring without repeating characters
Sep 24, 2024 am 06:21 AMProblem
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; } }
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!

Hot Article

Hot tools Tags

Hot Article

Hot Article Tags

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

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 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

Iceberg: The Future of Data Lake Tables

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

How to Share Data Between Steps in Cucumber
