Interesting String Problems

 1.  Longest common substring problem 

    Variant 1:      Longest common substring in two given strings. Let "aabcdefgh"  and  "ccbcdefff"  be two strings. Then the longest common substring is "bcdef".

    Variant  2: Longest repeating substring in a given string.  Let  "aabcdefghccbcdefff " be a string. Then, the longest repeating substring is again "bcdef".


2.   Longest palindromic substring

Given a string, the problem is to find the longest substring which is also a palindrome. Let "bananas" be a string, then the substring "anana" is the longest substring that is palindrome.

3.   String search / matching problem

Given a string S1 of size n and a string S2 of size m, where m < n, find the first or all the occurrences of string S2 in S1.  There are many algorithms to solve this problem in linear time. The most famous being Kunth-Morris-Pratt algorithm.

4. Strings  Anagram

Given two strings S1 and S2, find whether they are Anagram.

A string S1 is an Anagram of String S2 if S1 is formed by rearranging the letters of S2.

5. Reverse a string in place, e.g., "I LIKE IPHONE" -> "ENOHPI EKIL I".

6. Reverse characters of each word of string, e.g.,  "I LIKE IPHONE" -> "I EKIL ENOHPI".

7. Reverse a string such that the position of the words are reversed but the characters of the words are not reversed, e.g., "I LIKE IPHONE" -> "IPHONE LIKE I".

8. Find all the palindromes in a given string

Defintions, Data Structures, and Algorithms used for solving above problems

1.  Defining Substring, Subsequence, Prefix, and Suffix
2.  Defining Palindrome
3.  Difference between Substring and Subsequence
4.  Generalized Suffix Tree
5.  Dynamic Programming (DP)
      5.1   DP Practice Problems
      5.2   Tutorial on DP
      5.3   MIT Lecture Video