Diving into the realm of string manipulation and algorithmic challenges often uncovers captivating puzzles. One such intriguing problem is finding the length of the longest substring within a given string that consists of distinct characters. In this article, we'll embark on a journey to understand this problem, illustrate it with examples, and provide a Java solution to conquer it.
The Problem:
Given a string `S`, the task at hand is to determine the length of the longest substring within `S` that does not contain any repeating characters. In simpler terms, we're on a quest to identify the longest continuous sequence of characters in which no character appears more than once.
Examples:
Example-1:
Input: "abcabcbb" Output: 3 Explanation: The longest substring without repeating characters is "abc", with a length of 3. (code-box)
Example-2:
Input: "pwwkew" Output: 3 Explanation: The longest substring without repeating characters is "wke", with a length of 3. Note that "pwke" is a subsequence, not a substring. (code-box)
Example-3:
Input: "tmmzuxt" Output: 5 Explanation: The longest substring without repeating characters is "mzuxt", with a length of 5. (code-box)
Approach and Solution:
To surmount this challenge, we need a systematic approach that involves traversing the string while maintaining a sliding window that signifies the current substring under scrutiny. We can leverage a hashmap to store the last known index of each character encountered. This dynamic data structure aids in identifying whether a character has appeared earlier within the current window.
As we proceed through the string, if we stumble upon a character that has been encountered before and its last known index is within the current window, we must update the starting index of our sliding window to the subsequent position following the last occurrence of that character. This adjustment ensures that we consistently maintain a valid substring devoid of repeating characters.
To ascertain the length of the longest substring, we update the maximum length whenever we expand the window and discover a longer valid substring.
Java Solution:
package com.studyecart.hackerrank;
import java.util.Scanner;
public class LongestSubstring {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
int[] charIndexMap = new int[256]; // Assume extended ASCII characters
for (int end = 0, start = 0; end < n; end++) {
if (charIndexMap[s.charAt(end)] > start) {
start = charIndexMap[s.charAt(end)];
}
maxLength = Math.max(maxLength, end - start + 1);
charIndexMap[s.charAt(end)] = end + 1;
}
return maxLength;
}
public static void main(String[] args) {
LongestSubstring longestSubstring = new LongestSubstring();
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a string: ");
String input = scanner.nextLine();
int output = longestSubstring.lengthOfLongestSubstring(input);
System.out.println("Input: " + input);
System.out.println("Output: " + output);
}
}
(code-box)
Step-by-Step Explanation:
1. `public int lengthOfLongestSubstring(String s)`: This method takes a string `s` as input and returns an integer representing the length of the longest substring without repeating characters.
2. `int n = s.length();`: This line calculates the length of the input string `s` and stores it in the variable `n`.
3. `int maxLength = 0;`: This initializes the variable `maxLength` to keep track of the maximum length of the substring without repeating characters encountered so far.
4. `int[] charIndexMap = new int[256];`: This initializes an integer array `charIndexMap` of size 256, assuming extended ASCII characters. This array is used to store the last known index of each character encountered in the string.
5. `for (int end = 0, start = 0; end < n; end++) {`: This initiates a `for` loop that iterates through the characters of the input string `s`. The variable `end` represents the current position in the string, and the variable `start` is the starting position of the current substring being examined.
6. `if (charIndexMap[s.charAt(end)] > start) { ... }`: Inside the loop, this `if` condition checks if the current character at index `end` has been encountered before in the current substring (i.e., within the range of `start` to `end`). If it has, it means the character is repeating, and we need to update the `start` position to the next position after the last occurrence of that character.
7. `maxLength = Math.max(maxLength, end - start + 1);`: This line calculates the length of the current valid substring (from `start` to `end`) and compares it with the current `maxLength`. It updates `maxLength` if the current substring is longer.
8. `charIndexMap[s.charAt(end)] = end + 1;`: This updates the `charIndexMap` to store the current index `end + 1` for the character at index `end`.
9. The loop continues until all characters in the string have been examined.
10. Finally, the function returns the calculated `maxLength`, which represents the length of the longest substring without repeating characters.
This solution utilizes a sliding window approach along with the `charIndexMap` array to efficiently find the length of the desired substring. The sliding window moves forward as it examines characters, adjusting the `start` position whenever a repeating character is encountered, and updating the maximum length as needed.
Boost your Java programming skills with these top 10 beginner-friendly Java programs! Check them out Clickhere.
🚀 Elevate Your Career with Studyecart! 📚📊
🔥 Get instant job notifications and ace interviews with Studyecart. 📌
Download#StudyecartApp #CareerBoost
