String | Subsequence & Substring Last Updated : 26 Sep, 2023 Recent articles on String ! What is Substring Coding Problems on Substrings Easy Problems on Substrings Intermediate Problems on Substrings Hard Problems on Substrings Recent articles on Substrings What is Subsequence Coding Problems on Subsequence Easy Problems on Subsequence Intermediate Problems on Subsequence Hard Problems on Subsequence Recent articles on Subsequence What is a Substring? A substring is a contiguous part of a string, i.e., a string inside another string. In general, for an string of size n, there are n*(n+1)/2 non-empty substrings. For example, Consider the string “geeks”, There are 15 non-empty substrings. The subarrays are: g, ge, gee, geek, geeks, e, ee, eek, eeks, e, ek, eks, k, ks, ks What is a Subsequence? A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order of the remaining elements. More generally, we can say that for a sequence of size n, we can have ((2^n)-1) non-empty sub-sequences in total. For the same above example, there are 15 sub-sequences. They are: g, e, e, k, s, ge, ge, gk, gs, ee, ek, es, ek, es, ks, gee, gek, ges, gek, ges, gks, eek, ees, eks, eks, geek, gees, eeks, geeks Problems on Substring: Easy Problems Number of substrings of one string present in other Print all substring of a number without any conversion Substring Reverse Pattern Find the count of palindromic sub-string of a string in its sorted form Check if a string contains a palindromic sub-string of even length Count number of substrings with numeric value greater than X Check if the given string is K-periodic Maximum count of sub-strings of length K consisting of same characters Check whether given string can be generated after concatenating given strings Queries to answer the X-th smallest sub-string lexicographically Count of sub-strings of length n possible from the given string Longest sub string of 0’s in a binary string which is repeated K times Length of longest substring having all characters as K Maximum length palindromic substring such that it starts and ends with given char Find distinct characters in distinct substrings of a string Count all substrings having character K Reverse the given string in the range [L, R] Number of substrings that start with “geeks” and end with “for” Repeat substrings of the given String required number of times Split the binary string into substrings with equal number of 0s and 1s Intermediate Problems Reverse substrings between each pair of parenthesis Longest substring with K unique characters using Binary Search Jaro and Jaro-Winkler similarity Longest substring with atmost K characters from the given set of characters Lexicographically all Shortest Palindromic Substrings from a given string Shortest Palindromic Substring Count of all unique substrings with non-repeating characters Check if the given string is shuffled substring of another string Count of K-size substrings having palindromic permutations Count of substrings of length K with exactly K distinct characters Permutation of given string that maximizes count of Palindromic substrings Check if a substring can be Palindromic by replacing K characters for Q queries Count of ways to split given string into two non-empty palindromes Maximize partitions such that no two substrings have any common character Minimum replacements in a string to make adjacent characters unequal Count of substrings containing only the given character Count distinct substrings of a string using Rabin Karp algorithm Count of substrings having all distinct characters Smallest String consisting of a String S exactly K times as a Substring Minimize splits to generate monotonous Substrings from given String Hard Problems Count of Distinct Substrings occurring consecutively in a given String Check if a String contains Anagrams of length K which does not contain the character X Check if a Palindromic String can be formed by concatenating Substrings of two given Strings Minimum size substring to be removed to make a given string palindromic Count ways to split a Binary String into three substrings having equal count of zeros Applications of String Matching Algorithms Minimum operations to transform given string to another by moving characters to front or end Count characters to be shifted from the start or end of a string to obtain another string Lexicographic rank of a string among all its substrings Count of substrings of a string containing another given string as a substring Count substrings of same length differing by a single character from two given strings Extract substrings between any pair of delimiters Longest substring where all the characters appear at least K times | Set 3 Split a string into maximum number of unique substrings Find the last player to be able to flip a character in a Binary String Check if a string can be split into 3 substrings such that one of them is a substring of the other two Count ways to partition a number into increasing sequences of digits Maximum length of a substring required to be flipped repeatedly to make all characters of binary string equal to 0 XOR of all substrings of a given Binary String Sub-strings of a string that are prefix of the same string Problems on Subsequences: Easy Problems Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 Minimum number of palindromic subsequences to be removed to empty a binary string Find largest word in dictionary by deleting some characters of given string Longest Common Anagram Subsequence Number of subsequences as “ab” in a string repeated K times Maximum length subsequence possible of the form R^N K^N Check if two same sub-sequences exist in a string or not Longest subsequence where each character occurs at least k times Longest Uncommon Subsequence Find the lexicographically largest palindromic Subsequence of a String Intermediate Problems Maximum number of removals of given subsequence from a string Check if there exists any sub-sequence in a string which is not palindrome Number of balanced bracket subsequence of length 2 and 4 Minimum cost to make a string free of a subsequence Longest subsequence having greater corner values Longest subsequence with at least one character appearing in every string Distinct strings such that they contains given strings as sub-sequences Smallest Palindromic Subsequence of Even Length in Range [L, R] Minimum number of subsequences required to convert one string to another Find the length of the longest subsequence with first K alphabets having same frequency Hard Problems Number of ways to partition a string into two balanced subsequences Count common subsequence in two strings Total number of odd length palindrome sub-sequence around each center Minimum number of subsequences required to convert one string to another using Greedy Algorithm Longest Palindromic Subsequence of two distinct characters Longest subsequence with different adjacent characters Frequency of maximum occurring subsequence in given string Convert given string to another by minimum replacements of subsequences by its smallest character Minimize deletions in a Binary String to remove all subsequences of the form “0101” Subsequences of given string consisting of non-repeating characters Quick Links: ‘Practice Problems’ on Strings ‘Quizzes’ on Strings Share your thoughts in the comments Add Your Comment Please Login to comment...