Longest

Longest arithmetic progression in a sorted array

Problem Given a sorted array, find the longest arithmetic progression in the same. Solution Method 1 - Dynamic Programming Before solving this problem, let us solve a different problem first. How to find if a sorted array contains an arithmetic progression of length 3? This can be done by looping over the array and then finding numbers ‘i’ and ‘k’ on either side of current number ‘j’ such that ...

Longest Consecutive Sequence Problem

Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Examples Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. ...

Longest Increasing Subsequence LIS Problem

Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Examples Example 1: Input: A = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. ...

Longest Common Subsequence LCS 1 - Get Length

Problem Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings. ...

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

Longest Common Prefix in array of string

Problem Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". OR Given a sentence, give Longest Sequence Of Prefix Shared By All The Words In A String Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2. ...

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