Substring

Longest Palindromic Substring Problem

Problem Given a string s, return the longest palindromic substring in s. Incase of conflict, return the substring which occurs first ( with the least starting index ). Substring of string S: S[i...j] where 0 <= i <= j < len(S) Example Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. ...

Manachar’s Algorithm - Longest palindromic substring in linear time

Problem Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string We have already seen simple O(n^2) solution here - Longest Palindromic Substring Problem, but now lets look at Manacher’s Algorithm, which help us find the solution in linear time. Manacher’s Algorithm #TODO complete this

Longest Substring Without Repeating Characters Problem

Problem Given a string, find the length of the longest substring without repeating characters. Examples Example 1: Input: s = "aababcbb" Output: 3 Explanation: The longest substring without repeating characters is "abc". Example 2: Input: s = "cccc" Output: 1 Explanation: The longest substring without repeating characters is "c". ...

Longest Substring with K Distinct Characters

Problem Given a string, find the longest substring that contains only k unique or distinct characters. Examples Example 1: Input: S = "aabacbebebe", K = 3 Output: 7 Explanation: "cbebebe" is the longest substring with 3 distinct characters. Example 2: Input: S = "aaaa", K = 2 Output: -1 Explanation: There's no substring with 2 distinct characters. ...

Replace all spaces in c-style string with '%20'

Problem Write a C program that will replace all spaces with ‘%20′ Examples Input: s = "Mr John Smith" Output: "Mr%20John%20Smith Solution Method 1 - Count spaces and traverse from end The algorithm is as follows: Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as it is in the newly shifted location. Code C void replaceSpaces(char[] str, int length) { int spaceCount = 0, newLength, i = 0; for (i = 0; i < length; i++) { if (str[i] == ' ') { spaceCount++; } } newLength = length + spaceCount * 2; str[newLength] = '\0'; for (i = length - 1; i >= 0; i--) { if (str[i] == '') { str[newLength - 1] = '0'; str[newLength - 2] = '2'; str[newLength - 3] = '%'; newLength = newLength - 3; } else { str[newLength - 1] = str[i]; newLength = newLength - 1; } } } ...