Problems

LeetCode

Ukkonen’s Algorithm

Problem Statement: Build a Suffix tree in O(n)

Approach :

---

Longest common substring

Problem Statement:

Approach 1:
Build a generalized suffix tree for two strings concatenated with unique delimiters. The LCS in deepest internal node that has suffixes from both strings in its subtree.

O(n) for building tree and O(n) to find LCS.

Approach 2:
Use suffix automaton. This approach is space efficient and easy to implement.

fun SuffixAutomaton.lcs(str2: String) {
    var v = 0
    var l = 0
    var best = 0
    var bestPos = 0

    for((i, c) in str2.withIndex()) {
        while(v != 0 && c !in states[v].next) {
            v = states[v].link
            l = states[v].len
        }
        if(c in states[v].next) {
            v = states[v].next[c]!!
            l++
        }
        if(l > best) {
            best = l
            bestPos = i
        }
    }
    return str2.substring(bestPos - best + 1, bestPos + 1)
}

---

Longest Palindrome

Problem Statement: Given a string S find the longest substring which is a palindrome.

Approach:
Find the LCS in S and reverse of S.

---

Anagrams

Problem Statement: Find all distinct permutations of a string S.

Approach:

---

Combinations

Problem Statement: Find all distinct combinations of a string S. Unlike permutations, two combinations are same in they contain same characters in any order.

Approach:

---

Minimum substring

Problem Statement: Given two strings S and T. Find the minimum substring in S that contains all characters in T.

Approach:

---

P16

Problem Statement: Given a n x n matrix find all rows that match with some column.

Approach:

---

Running length encoding

Problem Statement: Compress a string by using the count of repeated characters.
Constraints — TC: O(n) & SC: O(1)

Approach:

---