String Algorithms

×

Home Discussions Write at Opengenus IQ

×

Generate all sub-strings of a string

We have explored the approach of generating / printing all sub-strings of a given String and have provided the implementation to do so. The time complexity to generate all substring is O(N^3) time and there are O(N^2) sub-strings for a string of length N.

Number of Substrings with distinct characters

We have explored various algorithms that will help us in determining the number of substrings that a string can have with distinct characters.

String Algorithms

Number of palindromic substrings in a string

A string is a palindrome when it reads the same backward as forward and a substring is a contiguous sequence of characters within the string. We have discussed multiple approaches to find the number of palindromic substrings in a given string.

Check if a string is a subsequence of another string

In this problem, we will see how we can check whether a string is a subsequence of another string. We have solved this in O(N) time using an efficient approach.

Number of substrings with exactly k distinct characters

In this problem, we are given a string and our job is to count the total number of substrings of the given string that contains exactly k distinct characters. We have explored 3 approaches to solve this.

Shift OR algorithm for String Matching

Shift OR algorithm uses bitwise techniques to check whether the given pattern is present in the string or not. It is efficient if the pattern length is lesser than the memory-word size of the machine

Convert one string to another by changing all occurrence of a character to another

We will be solving Check if one string can be converted to another by changing all occurrence of a character to another character problem using the Union and Find algorithm.

String Algorithms

Minimum number of operations to convert binary string to self-destructing

We will explore algorithms to find the Minimum number of operations to convert a binary string to a self-destructing string.

Longest common substring using rolling hash approach

We can solve the longest common substring problem using the rolling hash technique in O(N * log(N)^2) time and O(N) space which is significantly better than other approaches.

Find number of substrings with same first and last characters

You are given a string lets say "S" , you need to find the number of all contiguous substrings (part of "S") starting and ending with the same character.

Word Break Problem

In this article we are going to talk about a very interesting problem: Word Break Problem. This can be solved using Dynamic Programming [O(N^2) time, O(N^2) space].

Software Engineering

Reverse a String (word by word) in C

In this problem, we have reversed a string or text word by word in C. The strategy to do this is important and tests C implementation skill.

Number of times characters of a string is present in another string

In this article, we have explored the algorithm to find the Number of times characters of a string is present in another string. This can be solved in O(N^2) time.

First Unique Character in a String

In this article, we need to find first unique i.e non-repeating character in a given string and return the index or else if no such character exists we return -1.

String Matching using Bitset

In this article, we have explored how to solve string matching problem (find all occurences of string S1 in another string S2) using Bitset. It is a modification of the naive approach which takes O(L x P x logL) time complexity which improves to O(L x P / K) using bitset.

Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm

In this article, we have explored the difference between two popular string pattern searching algorithms: Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm.

Minimum characters added to the front of string to make it palindrome

In this problem, we have to formulate an algorithm to find the minimum number of characters to be added to the front of a string to make it a palindrome. To solve this efficiently in linear time O(N), we have to use longest prefix suffix of Knuth Morris Pratt pattern matching algorithm.

Minimum insertions to make the frequency of each character unique

We developed a string algorithm to find out the minimum number of insertions to be made in a string so that the frequency of each character is unique

Minimum deletions to make frequency of each character unique

The problem we will solve is that given a string s, we need to find the minimum number of characters to be deleted from s so that the frequency of each character in the string is unique.

Find if a string is a sub-string of another string

We have presented two approaches to check whether a string is a substring of another string namely naive method which takes O(N^2) time and efficient method using the concept of Rolling Hash which takes linear time O(N).

Rolling Hash

Rolling hash is an algorithmic technique which is used to prevent rehashing the whole string while calculating hash values of the substrings of a given string

Longest repeating and non overlapping substring in a string

We have to find the longest repeating and non-overlapping substring in a given string. Brute force approach takes O(N^3) time while Dynamic Programming takes O(N^2) time.

String hashing

Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity

Aho Corasick Algorithm

Aho Corasick algorithm is a string algorithm to find or search occurrences of k number of Patterns: P1 ,P2 .... Pk in a string text T. It is a modification over the KMP algorithm

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.