String DSA

String DSA | Let us see problems on String. We will discuss the following algorithms:- Rabin Karp Algorithm, KMP.

Table of Contents

• 1. Frequency of Characters
• 2. Palindrome Check
• 3. Check if a string is a subsequence of other
• 4. Check for Anagram
• 5. Leftmost Repeating Character
• 6. Leftmost Non-repeating element
• 7. Reverse Words in a String
• 8. Pattern Searching
  • Naive Pattern Searching
  • Improve Naive Algorithm for Pattern Searching having Distinct Characters in Pattern
• 9. Rabin Karp Algorithm
• 10. KMP Algorithm
  • a. Construct the Longest Proper Prefix Suffix Array (LPS)

---

String in Java can be represented in the following ways:-

1. Character Array/ArrayList

char[] arr = {'k', 'n', 'o', 'w', 'p'};

2. String class:- It is immutable and thread-safe. Immutable means any modification leads to the creation of a new object.

String str = "program";
String str = new String("program");

3. StringBuffer class:- It is mutable and thread-safe. Mutable means any modification will be done on the original object only and it won’t create a new object.

StringBuffer str = new StringBuffer("know")

4. StringBulder class:- It is also mutable but non-thread-safe. Therefore is better suitable for single-threaded applications.

StringBuilder str = new StringBuilder("know");

Methods of String

public class Test {
    public static void main(String[] args) {
        String str = "knowprogram";
        System.out.println(str.length());
        System.out.println(str.charAt(3));
        System.out.println(str.substring(2)); // 2 to end
        System.out.println(str.substring(2, 5)); // 2 to 4
    }
}

Output:-

11
w
owprogram
owp

How does Java handle String literal vs new String object? Java handles string literals by placing them in the string pool, allowing multiple references to the same literal to point to the same object, which saves memory. New string objects, created with the new keyword, are stored in the heap separately, even if they contain the same content as a string literal.

public class Test {
    public static void main(String[] args) {
        String str1 = "knowprogram";
        String str2 = "knowprogram";

        if (str1 == str2) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

        String str3 = new String("knowprogram");
        if (str1 == str3) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Output:-

Yes
No

The string contains() and equals() methods can be used to compare string content.

public class Test {
    public static void main(String[] args) {
        String str1 = "knowprogram";
        String str2 = "know";

        System.out.println(str1.contains(str2)); // true
        System.out.println(str1.equals(str2)); // false
    }
}

String s1.compareTo(s2) returns 0 if both s1 and s2 are the same (content/data), a positive value if s1 is lexicographically greater than s2, and -negative if s2 is lexicographically greater than s1. The return value will be the difference of the first unmatched character.

public class Test {
    public static void main(String[] args) {
        String str1 = "knowprogram";
        String str2 = "hello";

        System.out.println(str1.compareTo(str2)); // 3
        System.out.println(str2.compareTo(str1)); // -3
    }
}

The indexOf() method returns the first index of a given character/string either from the beginning (default) or from the given index.

public class Test {
    public static void main(String[] args) {
        String str1 = "knowprogram";
        String str2 = "pro";

        // indexOf(String str)
        System.out.println(str1.indexOf(str2)); // 4

        // indexOf(int ch)
        System.out.println(str1.indexOf('r')); // 5

        // indexOf(String str, int fromIndex)
        // indexOf(char ch, int fromIndex)
        System.out.println(str1.indexOf("r", 6)); // 8
    }
}

Since strings are immutable therefore it creates a new object in each modification operation.

public class Test {
    public static void main(String[] args) {
        String str1 = "know";
        String str2 = str1;

        str1 = str1 + "program";
        // or
        // str1 = str1.concat("program");

        System.out.println(str1); // knowprogram
        System.out.println(str1 == str2); // false
    }
}

1. Frequency of Characters

Print the frequency of characters in a sorted array in a string of lowercase alphabets.

I/P: string = “knowprogram”
O/P: {a=1, g=1, k=1, m=1, n=1, o=2, p=1, r=2, w=1}

import java.util.LinkedHashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        String str = "knowprogram";
        System.out.println(frequency(str));
    }

    private static Map<Character, Integer> frequency(String str) {
        int[] chars = new int[26];
        for (int i = 0; i < str.length(); i++) {
            chars[str.charAt(i) - 'a']++;
        }
        // to return
        Map<Character, Integer> frequency = new LinkedHashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != 0) {
                frequency.put((char) ('a' + i), chars[i]);
            }
        }
        return frequency;
    }
}

Time complexity O(n), and space complexity O(1) [Because both array and frequency have fixed size 26].

2. Palindrome Check

For a given string check whether it is palindrome or not. If the reverse of a string is the same as are original string then the string is a palindrome. Problem: 125

String = “ABCDCBA” => Yes
String = “ABBA” => Yes
String = “program” => No

Using the pre-defined reverse() method of StringBuilder/StringBuffer class:-

public class Test {
    public static void main(String[] args) {
        System.out.println(isPalindrome("know")); // false
        System.out.println(isPalindrome("abcdcba")); // true
    }

    private static boolean isPalindrome(String str) {
        StringBuilder rev = new StringBuilder();
        rev.reverse();
        return str.equals(rev.toString());
    }
}

Time complexity O(n) and space complexity O(n).

We can compare characters from the start and end if they are all are same then the string is a palindrome. Through this, we can achieve Time complexity O(n) and space complexity O(1).

private static boolean isPalindrome(String s) {
    for (int begin = 0, end = s.length() - 1; begin < end; begin++, end--) {
        if (s.charAt(begin) != s.charAt(end)) {
            return false;
        }
    }
    return true;
}

3. Check if a string is a subsequence of other

Substring of a string can be achieved by removing 0 or more characters, and unremoved characters should appear in the same order as they were in the original order. All subsequences of “ABC” are:- “”, “A”, “B”, “C”, “AB”, “AC”, “BC”, “ABC”. The total number of subsequences in a given string of length n is 2^n because for every character there are two choices:- either keep it or not.

s1 = “ABCD”, s2 = “AD”; O/P: true
s1 = “ABCDE”, s2 = “AED”; O/P: false

A naive solution can be to generate all subsequences and compare a given string with subsequences. Time complexity will be O(2^n * n). But we can optimize this with below idea:-

Take two indexes i and j for both strings, and compare s1[i] with s2[j]. If they matched then move forward in both strings (increment both i and j), else move forward only in string s1. If we have iterated all characters of s2 it means s2 all characters are available in the s1 in original order, so return true.

If s2.length() > s1.length() then s2 is never going to be a subsequence of s1 therefore we will iterate only till s1.length().

public class Test {
    public static void main(String[] args) {
        System.out.println(isSubsequence("ABCD", "AD")); // true
        System.out.println(isSubsequence("ABCDE", "AED")); // false

    }

    // iterative solution
    private static boolean isSubsequence(String s1, String s2) {
        int j = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
        }
        return j == s2.length();
    }
}

Time complexity O(n) and space complexity O(1).

We can do the same through a recursive approach. In a recursive solution, we can check from the last index. If both characters matched then decrement the index for both strings, else decrement only in s1.

public class Test {
    public static void main(String[] args) {
        String s1 = "ABCD";
        String s2 = "AD";
        System.out.println(isSubsequence(s1, s2, s1.length() - 1, s2.length() - 1)); 
        // true
    }

    // recursive solution
    private static boolean isSubsequence(String s1, String s2, int n, int m) {
        if (m == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }
        if (s1.charAt(n) == s2.charAt(m)) {
            return isSubsequence(s1, s2, n - 1, m - 1);
        }
        return isSubsequence(s1, s2, n - 1, m);
    }
}

Time complexity O(n) and space complexity O(m + n).

4. Check for Anagram

Anagram means permutations of each other or not. Both strings should have the same characters and the frequency of characters should be matched, however, the order of appearance may differ.

s1 = “listen”, s2 = “silent”; O/P: Yes
s1 = “aaacb”, s2 = “cabaa”; O/P: Yes
s1 = “aab”, s2 = “bab”; O/P: No

Steps:-

• Length Check: If both strings have different lengths, they can’t be anagrams.
• Frequency Count: Create an array count to keep track of character frequencies. Use char[256] array. Iterate through both strings simultaneously:
  • Increment the count for characters in s1.
  • Decrement the count for characters in s2.
• Validation: Check the count array. If all values are zero, the strings are anagrams. If any value is non-zero, they are not.

The char[256] array is used to cover all possible characters in the extended ASCII set, which includes 256 characters. This ensures that the algorithm can handle any character, including special characters and punctuation when checking if two strings are anagrams.

public class Test {
    private final static int CHAR = 256;

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent")); // true
    }

    private static boolean isAnagram(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] chars = new int[CHAR];

        for (int i = 0; i < s1.length(); i++) {
            chars[s1.charAt(i)]++;
            chars[s2.charAt(i)]--;
        }

        // check for 0
        for (int k : chars) {
            if (k != 0) {
                return false;
            }
        }

        return true;
    }
}

Time complexity O(n) and space complexity O(1).

5. Leftmost Repeating Character

The string is given with possible repetition. Find the leftmost repeating character (which occurs more than once). Return the index of that leftmost character. Examples:-

• String = “abbcc”; O/P: 1 (Both character ‘b’ and ‘c’ occur 2 times, but ‘b’ is leftmost compared to ‘c’).
• String = “abccb”; O/P: 1 (Both character ‘b’ and ‘c’ occur 2 times, but ‘b’ is leftmost compared to ‘c’).
• String = “abcd”; O/P: -1 (There is no repeating character)

Naive approach: Traverse through every character, and for every character check if it repeats. Time complexity will be O(n^2) and space complexity O(1).

The efficient solution can be:- Use characters and indexes and store their frequencies. We need two traversals. In the first traversal, store the count/frequency of all the characters. In the second traversal we find the first character having count/frequency > 1.

public class Test {
    private final static int CHAR = 256;

    public static void main(String[] args) {
        System.out.println(leftMostRepeatingChar("adcbbc")); // 2
    }

    private static int leftMostRepeatingChar(String s) {
        int[] count = new int[CHAR];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] > 1) {
                return i;
            }
        }

        return -1;
    }
}

Time complexity O(n), and space complexity O(1).

How can we solve this problem in a single traversal? The idea is to traverse the string from left to right and keep track of the first occurrence of every character. Use character as an index.

import java.util.Arrays;

public class Test {
    private final static int CHAR = 256;

    public static void main(String[] args) {
        System.out.println(leftMostRepeatingChar("adcbbc")); // 2
    }

    private static int leftMostRepeatingChar(String string) {
        int[] fIndex = new int[CHAR];
        Arrays.fill(fIndex, -1);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < string.length(); i++) {
            int fi = fIndex[string.charAt(i)];
            if (fi == -1) {
                fIndex[string.charAt(i)] = i;
            } else {
                res = Math.min(res, fi);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Time complexity O(n), and auxiliary space O(1).

Another approach is to traverse from right to left. Create a visited array, it should be a boolean array, not an integer array. Traverse through the characters from left, if the character is already visited then update the result else mark it as visited. Since we are traversing from right to left therefore result with have the leftmost visited character.

public class Test {
    private final static int CHAR = 256;

    public static void main(String[] args) {
        System.out.println(leftMostRepeatingChar("adcbbc")); // 2
    }

    private static int leftMostRepeatingChar(String s) {
        boolean[] visited = new boolean[CHAR];
        int res = -1;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (visited[s.charAt(i)]) {
                res = i;
            } else {
                visited[s.charAt(i)] = true;
            }
        }
        return res;
    }
}

Time complexity O(n), and auxiliary space O(1).

6. Leftmost Non-repeating element

The string is given with possible repetition. Find the leftmost non-repeating character. Examples:-

• String = “swiss”; O/P: 1 (Both characters ‘w’, and ‘i’ occur only 1 time, but ‘w’ is leftmost)
• String = “abbcc”; O/P: 0 (Character ‘a’ occurs only 1 time).
• String = “bcdcb”; O/P: 3 (Character ‘d’ occurs only 1 time).
• String = “abcabc”; O/P: -1 (There is no non-repeating character)

Create a count array of size 256. Traverse through the character and update the count. Again traverse the characters and if the count of characters is 1 then return the index.

public class Test {
    public static void main(String[] args) {
        System.out.println(leftMostNonRepeatingChar("adcbbc")); // 0
    }

    private static int leftMostNonRepeatingChar(String s) {
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] == 1) {
                return i;
            }
        }
        return -1;
    }
}

Time complexity O(n) and auxiliary space O(1).

How it can be done in a single traversal? The below program has 2 traversals, the first traversal is for a string, and another is for a char array whose size (256) is constant therefore we can consider this solution as a single traversal.

• Create an array of size 256. Initialize all elements with -1.
• It will store indexes of non-repeating characters.
• For repeating character store -2.
• The character that was never seen will have -1.

import java.util.Arrays;

public class Test {
    private final static int CHAR = 256;

    public static void main(String[] args) {
        System.out.println(leftMostNonRepeatingChar("adcbbc")); // 0
    }

    private static int leftMostNonRepeatingChar(String s) {
        int[] fi = new int[CHAR];
        Arrays.fill(fi, -1);

        // Populate the first occurrence index array
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i);
            if (fi[ch] == -1) {
                fi[ch] = i;
            } else {
                fi[ch] = -2;
            }
        }

        int res = Integer.MAX_VALUE;
        // Find the smallest index in fi[] which is non-repeating
        for (int k : fi) {
            if (k >= 0) {
                res = Math.min(res, k);
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Time complexity O(n) and auxiliary space O(1).

7. Reverse Words in a String

String = “Welcome to Java”; O/P: “Java to Welcome”.
String = “Hello, how are you”; O/P: “you are how Hello,”.
String = “Hi”; O/P: “Hi”

Modify the same character array instead of creating another one.

Naive Solution using Stack:-

• Create a stack
• Push words one by one to the stack
• Pop words from the stack and append the output.

However, it requires O(n) auxiliary space.

Efficient solution using Constant auxiliary space:-

• Traverse through the given character array. Assume string = “abc bcd ef”
• Reverse each word, based on space character. Now, string = “cba dcb fe”
• Reverse a complete string. Now, string = “ef bcd abc”

public class Test {
    public static void main(String[] args) {
        System.out.println(reverseWords("abc bcd ef"));
    }

    private static String reverseWords(String s) {
        char[] str = s.toCharArray();
        int start = 0;
        for (int end = 0; end < str.length; end++) {
            // considering words are separated by one space
            if (str[end] == ' ') {
                reverse(str, start, end - 1);
                start = end + 1;
            }
        }
        // reverse last word
        reverse(str, start, str.length - 1); 

        // reverse complete string
        reverse(str, 0, str.length - 1);

        return String.valueOf(str);
    }

    private static void reverse(char str[], int low, int high) {
        while (low <= high) {
            // swap
            char ch = str[low];
            str[low] = str[high];
            str[high] = ch;

            low++;
            high--;
        }
    }
}

8. Pattern Searching

For a given string and a pattern, find all occurrences of the pattern in the string. Examples:-

• Text: “mississippi”, Pattern: “iss” Occurrences: [1, 4]; Pattern is present at 1st and 4th indexes.
• Text: “banana”, Pattern: “ana” Occurrences: [1, 3]
• Text: “abracadabra”, Pattern: “abra” Occurrences: [0, 7]
• Text: “testtext”, Pattern: “test” Occurrences: [0]
• Text: “aaaaa”, Pattern: “aa” Occurrences: [0, 1, 2, 3] (Pattern is present everywhere).
• Text: “abcabad”, Pattern: “abcd” Occurrences: -1 (Pattern is not present).

It is a very common problem in computer science. Examples:- File searching, DNA matching, and regular expression searching. Therefore there exist multiple algorithms for its solution.

Consider m as pattern length and n as text text where 1 <= m <= n.

Algorithm	Time Complexity	Preprocessing
Naive	O((n – m + 1) * m)	No Preprocessing
Naive (Distinct Characters)	O(n)	No Preprocessing
Rabin-Karp	O((n – m + 1) * m) (Better on Average)	Preprocess Pattern
KMP	O(n)	Preprocess Pattern
Boyer-Moore	O(mn) (Worst Case), often O(n/m) in practice	Preprocess Pattern
Suffix Tree	O(m)	Preprocess Text
Z Algorithm	O(n + m)	Preprocess Text

Naive Pattern Searching

This approach searches for all occurrences of a given pattern in a given string using a sliding window approach. It iterates through the main string, comparing substrings of equal length to the pattern. When a match is found, it records the starting index.

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        System.out.println(patternSearch("mississippi", "iss")); // [1, 4]
    }

    private static List<Integer> patternSearch(String text, String pattern) {
        int m = pattern.length(), n = text.length();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (pattern.charAt(j) != text.charAt(i + j)) {
                    break;
                }
            }
            if (j == m) {
                result.add(i);
            }
        }
        return result;
    }
}

Time complexity: O((n – m + 1) * m). The first for loop runs for (n – m + 1) and the second loop runs for m times. It has auxiliary space O(1).

Improve Naive Algorithm for Pattern Searching having Distinct Characters in Pattern

We are considering that the pattern contains distinct characters (doesn’t have duplicates). Example:- Text = “ABCABCDABCD”, Pattern = “ABCD”. O/P: [3, 7]

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        System.out.println(patternSearch("ABCABCDABCD", "ABCD"));
    }

    private static List<Integer> patternSearch(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < n - m;) {
            int j;
            for (j = 0; j < m; j++) {
                if (pattern.charAt(j) != text.charAt(i + j)) {
                    break;
                }
            }

            if (j == m) {
                result.add(i);
            }

            if (j == 0) {
                i++;
            } else {
                i = i + j;
            }
        }
        return result;
    }
}

Time complexity O(n).

9. Rabin Karp Algorithm

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find any one of a set of pattern strings in a text. It is particularly effective when searching for multiple patterns or when the pattern length is short relative to the text.

Key Points:-

• Hashing: It computes a hash value for the pattern and the text substrings of the same length. It uses a rolling hash function to efficiently compute hash values for the subsequent substrings.
• Matching: If the hash values match, it performs a detailed comparison of the substrings. If the detailed comparison also matches, it confirms the occurrence of the pattern.

Steps:

• Compute the hash value of the pattern.
• Compute the hash value of the first substring of the text with the same length as the pattern.
• Slide the pattern over the text: Recompute the hash for the next substring using the rolling hash function. Compare the hash values. If they match, check the substrings for an exact match.
• Return the starting indices where the pattern occurs in the text.

We will use the following terms:-

• p: Hash value of pattern
• t: Hash value of current window of text

public class Test {
    private final static int d = 256; // Number of characters in the input alphabet
    private final static int q = 101; // A prime number

    public static void main(String[] args) {
        String text = "ABCCBABABAC";
        String pattern = "BAB";
        search(pattern, text);
    }

    public static void search(String pattern, String text) {
        int m = pattern.length();
        int n = text.length();
        int i, j;
        int p = 0; // Hash value for pattern
        int t = 0; // Hash value for text
        int h = 1;

        // Calculate the value of h (d^(m-1) % q)
        for (i = 0; i < m - 1; i++) {
            h = (h * d) % q;
        }

        // Calculate the hash value of the pattern and first substring of text
        for (i = 0; i < m; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        // Slide the pattern over the text one by one
        for (i = 0; i <= n - m; i++) {
            // Check the hash values
            if (p == t) {
                // Hash values match, check the characters
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        break;
                    }
                }

                if (j == m) {
                    System.out.println("Pattern found at index " + i);
                }
            }

            // Calculate hash value for the next substring of text
            if (i < n - m) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;

                // We might get negative values, convert to positive
                if (t < 0) {
                    t = (t + q);
                }
            }
        }
    }
}

The average time complexity of the Rabin-Karp algorithm is O(n + m), but in the worst case (with many hash collisions), it can be O(nm). The space complexity of the Rabin-Karp algorithm is O(1), as it uses a constant amount of extra space regardless of the input size.

10. KMP Algorithm

a. Construct the Longest Proper Prefix Suffix Array (LPS)

Understanding the Longest Proper Prefix Suffix Array (LPS) is a prerequisite for the KMP Algorithm.

String = “abc”
Proper prefixes of the string:- “”, “a”, “ab”
Suffixes of the given string:- “”, “c”, “bc”, “abc”

Note that “abc” itself is not the proper prefix of “abc”. Whenever we add word “proper” it means resultant length should be < actual length.

String = “abcd”
Proper prefixes are:- “”, “a”, “ab”, “abc”
Suffixes are:- “”, “d”, “cd”, “bcd”, “abcd”

For a given string we have to find out the longest proper prefix which is also suffix at every point.

String = “ababab”
lps[] = {0, 0, 1, 2, 3, 4}

Explanation for string = “ababab”:

• Index 0 => “a”: No proper prefix = suffix → LPS[0] = 0
• Index 1 => “ab”: No proper prefix = suffix → LPS[1] = 0
• Index 2 => “aba”: Prefix “a” = Suffix “a” → LPS[2] = 1
• Index 3 => “abab”: Prefix “ab” = Suffix “ab” → LPS[3] = 2
• Index 4 => “ababa”: Prefix “aba” = Suffix “aba” → LPS[4] = 3
• Index 5 => “ababab”: Prefix “abab” = Suffix “abab” → LPS[5] = 4

String = “abacabad”
lps[] = {0, 0, 1, 0, 1, 2, 3, 0}

• Index 0 => “a”: No proper prefix = suffix → LPS[0] = 0
• Index 1 => “ab”: No proper prefix = suffix → LPS[1] = 0
• Index 2 => “aba”: Prefix “a” = Suffix “a” → LPS[2] = 1
• Index 3 => “abac”: No proper prefix = suffix → LPS[3] = 0
• Index 4 => “abaca”: Prefix “a” = Suffix “a” → LPS[4] = 1
• Index 5 => “abacab”: Prefix “ab” = Suffix “ab” → LPS[5] = 2
• Index 6 => “abacaba”: Prefix “aba” = Suffix “aba” → LPS[6] = 3
• Index 7 => “abacabad”: No proper prefix = suffix → LPS[7] = 0

String = “abbabb”;
lps[] = {0, 0, 0, 1, 2, 3}

• Index 0 => “a”: No proper prefix = suffix → LPS[0] = 0
• Index 1 => “ab”: No proper prefix = suffix → LPS[1] = 0
• Index 2 => “abb”: No proper prefix = suffix → LPS[2] = 0
• Index 3 => “abba”: Prefix “a” = Suffix “a” → LPS[3] = 1
• Index 4 => “abbab”: Prefix “ab” = Suffix “ab” → LPS[4] = 2
• Index 5 => “abbabb”: Prefix “abb” = Suffix “abb” → LPS[5] = 3

String = “ababc”
lps[] = {0, 0, 1, 2, 0}

String = “aaaa”
lps[] = {0, 1, 2, 3} All characters in string are same.

String = “abcd”
lps[] = {0, 0, 0, 0} All characters in string are different.

Naive program to find the LPS array for a given string.

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        String string = "abacabad";
        System.out.println(Arrays.toString(lps(string)));
    }

    private static int[] lps(String s) {
        int[] lps = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            lps[i] = longPropPreSuff(s, i + 1);
        }
        return lps;
    }

    private static int longPropPreSuff(String s, int n) {
        for (int len = n - 1; len > 0; len--) {
            boolean flag = true;
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) != s.charAt(n - len + i)) {
                    flag = false;
                }
            }
            if (flag == true) {
                return len;
            }
        }
        return 0;
    }
}

Time complexity O(n^3)

How can we optimize it? We can use already computed LPS value. At index i, we have already computed LPS from 0 to i-1. Therefore we can use existing computed LPS value.

Basic Idea:

1. If len = lps[i-1] and str[len] and str[i] are same then lps[i] = len + 1
2. If str[i] and str[len] are not same.

• If len == 0, then lps[i] = 0
• Else, we recursively apply lps[] as len = lps[len-1] then compare str[i] with str[len].

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search