Longest Substring
Shamikksha has a string to play with her friend. She wants to find the length of the longest Substring.
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Sample input
abcabcbb
Sample output
3
Program:
def length_of_longest_substring(s):
n = len(s)
ans = 0
char_map = {}
i = 0
for j in range(n):
if s[j] in char_map:
i = max(char_map[s[j]], i)
ans = max(ans, j - i + 1)
char_map[s[j]] = j + 1
return ans
s = input()
print(length_of_longest_substring(s))
Explanation:
1)Function Definition: The function length_of_longest_substring(s) is defined with s as the input string.
2)Length Calculation: n = len(s) calculates the length of the string s and stores it in n.
3)Initialize Variables: ans = 0 initializes the variable ans to 0, which will eventually hold the length of the longest substring without repeating characters. char_map = {} initializes an empty dictionary that will be used to store the characters in the current window of the string (the substring being examined) and their indices.
4)Initialize Starting Point: i = 0 sets the starting point of the window (substring) at the first character of the string s.
5)Start Loop: The loop for j in range(n): runs through each character in the string s.
6)Check for Repeated Character: The if statement if s[j] in char_map: checks if the character s[j] is already in the current window (substring). If it is, this means we have a repeated character.
7)Move Starting Point: If s[j] is a repeated character, then i = max(char_map[s[j]], i) moves the starting point of the window to the right of the previous occurrence of s[j] (or keeps it as is, if the previous occurrence of s[j] is outside the current window).
8)Update Answer: ans = max(ans, j - i + 1) updates ans if the length of the current window (j - i + 1) is greater than the current value of ans.
9)Update Character Map: char_map[s[j]] = j + 1 updates the dictionary with the current character s[j] and its next index j + 1.
10)Return Answer: After the loop has run through all characters in the string, the function returns ans, which is the length of the longest substring without repeating characters.
11)Take User Input: s = input() takes a string as input from the user.
12)Print Answer: print(length_of_longest_substring(s)) prints the length of the longest substring without repeating characters in the user's string.
0 Comments