String Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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.

Algorithms

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

Algorithms

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.

Algorithms

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

Algorithms

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

Algorithms

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.

Algorithms

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

Algorithms

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

Algorithms

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.

Algorithms

Boyer Moore String Search Algorithm

Boyer Moore string search algorithm is an efficient string searching algorithm which was developed by Robert S. Boyer and J Strother Moore in 1977. The time complexity is linear in terms of length of data to be searched and preprocessing complexity is linear as well

Algorithms

KMP (Knuth-Morris-Pratt) Algorithm

Given a string S of length n and a pattern P of length m , you have to find all occurences of pattern P in string S provided n > m. Knuth Morris Pratt algorithm is an efficient pattern searching algorithm. Time and space complexity of KMP algorithm is O(m + n) linear.

Algorithms

Rabin-Karp Pattern Searching Algorithm

Rabin-Karp Algorithm is an efficient string pattern searching algorithm that utilizes the technique of hashing to search for patterns in a string in linear time by using a clever way of calculating hashes. This algorithm has been developed by Richard M. Karp and Michael O. Rabin in 1987.

String Algorithms

Algorithm to find the maximum occurring character in a string

Algorithm Pseudocode Complexity Implementation Applications Reading time: 15 minutes | Coding time: 5 minutes One approach to solve this problem would be to sort the input string and then traverse through the sorted string

String Algorithms

Z Algorithm function

The Z-function for a string S of length N is an array of length N where the i th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of S.

suffix array

Suffix Array

A Suffix Array contains integers that represent the starting indices of all the suffixes of a given string, after the aforementioned suffixes have been sorted. There are two approaches to compute: O(N^2 * log N) and O(N * log N * log N) approach. Locate every occurrence of a pattern within a string