📌 Top 10 String & Pattern Matching Questions Asked in Companies

📌 1. Reverse Words in a String

Asked in: Amazon, Google, TCS

 Given a string S, reverse the order of words without reversing individual words.

📌 2. Check if a String is a Palindrome

Asked in: Flipkart, Wipro, TCS

 Determine if a given string S is a palindrome (reads the same forward and backward).

📌 3. Check if Two Strings are Anagrams

Asked in: Amazon, Google, Microsoft

 Given two strings S1 and S2, check if they are anagrams (contain the same characters in any order).

📌 4. Find the Longest Palindromic Substring

Asked in: Google, Amazon, Flipkart

 Given a string S, find the longest substring that is a palindrome.

📌 5. Implement the KMP Algorithm for Pattern Matching

Asked in: Amazon, Google, Microsoft

 Given a string S and a pattern P, implement KMP (Knuth-Morris-Pratt) algorithm to find all
occurrences of P in S efficiently.

📌 6. Implement the Rabin-Karp Algorithm for String Matching

Asked in: Adobe, Google, TCS

 Given a string S and a pattern P, implement Rabin-Karp algorithm to search for P in S using hashing.

📌 7. Find the Longest Common Prefix (LCP) Among Strings

Asked in: Microsoft, Google, Amazon

 Given an array of strings, find the longest common prefix among them.

📌 8. Find All Occurrences of a Pattern in a Text Using Z-Algorithm

Asked in: Flipkart, Amazon, TCS

 Given a text S and pattern P, use Z-Algorithm to efficiently find all occurrences of P in S.

📌 9. Build a Suffix Array for a Given String

Asked in: Google, Microsoft, Amazon

 Construct a suffix array for a given string S, which helps in efficient pattern matching.

📌 10. Find the Longest Repeated Substring Using Suffix Arrays & LCP
Asked in: Google, Facebook, Microsoft

 Given a string S, find the longest repeated substring using suffix arrays and LCP (Longest Common
Prefix).
📌 1. Reverse Words in a String Asked in: Amazon, Google, TCS Given a string S,
reverse the order of words without reversing individual words.

C++ Solution
#include <bits/stdc++.h>
using namespace std;

string reverseWords(string s) {
stringstream ss(s);
string word, result = "";
vector<string> words;

while (ss >> word)

words.push_back(word);

reverse([Link](), [Link]());

for (int i = 0; i < [Link](); i++) {

result += words[i];
if (i != [Link]() - 1) result += " ";
}
return result;
}

int main() {
string s = "Hello World from Syntax Error";
cout << reverseWords(s) << endl;
return 0;
}

Java Solution
import [Link].*;

public class ReverseWords {

public static String reverseWords(String s) {
String[] words = [Link]().split("\\s+");
[Link]([Link](words));
return [Link](" ", words);
}

public static void main(String[] args) {

String s = "Hello World from Syntax Error";
[Link](reverseWords(s));
}
}

Python Solution
def reverse_words(s):
words = [Link]()
return " ".join(reversed(words))

# Example usage
s = "Hello World from Syntax Error"
print(reverse_words(s))

📌 2. Check if a String is a Palindrome

Asked in: Flipkart, Wipro, TCS

 Determine if a given string S is a palindrome (reads the same forward and backward).

C++ Solution
#include <bits/stdc++.h>
using namespace std;

string reverseWords(string s) {
stringstream ss(s);
string word, result = "";
vector<string> words;

while (ss >> word)

words.push_back(word);

reverse([Link](), [Link]());

for (int i = 0; i < [Link](); i++) {

result += words[i];
if (i != [Link]() - 1) result += " ";
}
return result;
}

int main() {
string s = "Hello World from Syntax Error";
cout << reverseWords(s) << endl;
return 0;
}

Java Solution
import [Link].*;

public class ReverseWords {

public static String reverseWords(String s) {
String[] words = [Link]().split("\\s+");
[Link]([Link](words));
return [Link](" ", words);
}

public static void main(String[] args) {

String s = "Hello World from Syntax Error";
[Link](reverseWords(s));
}
}

Python Solution
def reverse_words(s):
words = [Link]()
return " ".join(reversed(words))

# Example usage
s = "Hello World from Syntax Error"
print(reverse_words(s))

📌 3. Check if Two Strings are Anagrams

Asked in: Amazon, Google, Microsoft

 Given two strings S1 and S2, check if they are anagrams (contain the same characters in any order).

C++ Solution
#include <bits/stdc++.h>
using namespace std;

bool areAnagrams(string s1, string s2) {

if ([Link]() != [Link]()) return false;
sort([Link](), [Link]());
sort([Link](), [Link]());
return s1 == s2;
}

int main() {
string s1 = "listen", s2 = "silent";
if (areAnagrams(s1, s2))
cout << "Anagrams" << endl;
else
cout << "Not Anagrams" << endl;
return 0;
}

Java Solution
import [Link];

public class AnagramCheck {

public static boolean areAnagrams(String s1, String s2) {
if ([Link]() != [Link]()) return false;
char[] arr1 = [Link]();
char[] arr2 = [Link]();
[Link](arr1);
[Link](arr2);
return [Link](arr1, arr2);
}

public static void main(String[] args) {

String s1 = "listen", s2 = "silent";
if (areAnagrams(s1, s2))
[Link]("Anagrams");
else
[Link]("Not Anagrams");
}
}

Python Solution
def are_anagrams(s1, s2):
return sorted(s1) == sorted(s2)

# Example usage
s1, s2 = "listen", "silent"
if are_anagrams(s1, s2):
print("Anagrams")
else:
print("Not Anagrams")

📌 4. Find the Longest Palindromic Substring

Asked in: Google, Amazon, Flipkart

 Given a string S, find the longest substring that is a palindrome.

C++ Solution (Expand Around Center)

#include <bits/stdc++.h>
using namespace std;

string expandFromCenter(string s, int left, int right) {

while (left >= 0 && right < [Link]() && s[left] == s[right]) {
left--;
right++;
}
return [Link](left + 1, right - left - 1);
}

string longestPalindrome(string s) {
if ([Link]()) return "";
string longest = "";
for (int i = 0; i < [Link](); i++) {
string odd = expandFromCenter(s, i, i); // Odd-length
palindrome
string even = expandFromCenter(s, i, i + 1); // Even-length
palindrome
if ([Link]() > [Link]()) longest = odd;
if ([Link]() > [Link]()) longest = even;
}
return longest;
}

int main() {
string s = "babad";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) <<
endl;
return 0;
}

Java Solution (Expand Around Center)

public class LongestPalindromicSubstring {
public static String expandFromCenter(String s, int left, int right) {
while (left >= 0 && right < [Link]() && [Link](left) ==
[Link](right)) {
 left--;
right++;
}
return [Link](left + 1, right);
}

public static String longestPalindrome(String s) {

if ([Link]()) return "";
String longest = "";
for (int i = 0; i < [Link](); i++) {
String odd = expandFromCenter(s, i, i); // Odd-length
palindrome
String even = expandFromCenter(s, i, i + 1); // Even-length
palindrome
if ([Link]() > [Link]()) longest = odd;
if ([Link]() > [Link]()) longest = even;
}
return longest;
}

public static void main(String[] args) {

String s = "babad";
[Link]("Longest Palindromic Substring: " +
longestPalindrome(s));
}
}

Python Solution (Expand Around Center)

def expand_from_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

def longest_palindrome(s):
longest = ""
for i in range(len(s)):
odd = expand_from_center(s, i, i) # Odd-length palindrome
even = expand_from_center(s, i, i + 1) # Even-length palindrome
longest = max(longest, odd, even, key=len)
return longest

# Example usage
s = "babad"
print("Longest Palindromic Substring:", longest_palindrome(s))

📌 5. Implement the KMP Algorithm for Pattern Matching

Asked in: Amazon, Google, Microsoft

Given a string S and a pattern P, implement KMP (Knuth-Morris-Pratt) algorithm to find all occurrences of P
in S efficiently
C++ Solution
#include <bits/stdc++.h>
using namespace std;

// Function to compute LPS array

vector<int> computeLPS(string pattern) {
int m = [Link]();
vector<int> lps(m, 0);
int len = 0, i = 1;

while (i < m) {
if (pattern[i] == pattern[len]) {
lps[i++] = ++len;
} else {
if (len) len = lps[len - 1];
else lps[i++] = 0;
}
}
return lps;
}

// KMP Pattern Matching Algorithm

void KMP(string text, string pattern) {
int n = [Link](), m = [Link]();
vector<int> lps = computeLPS(pattern);

int i = 0, j = 0; // i -> text, j -> pattern

while (i < n) {
if (text[i] == pattern[j]) {
i++, j++;
}
if (j == m) {
cout << "Pattern found at index " << i - j << endl;
j = lps[j - 1];
} else if (i < n && text[i] != pattern[j]) {
j ? j = lps[j - 1] : i++;
}
}
}

int main() {
string text = "ababcababcabc", pattern = "abc";
KMP(text, pattern);
return 0;
}

Java Solution
import [Link].*;

public class KMPAlgorithm {

public static int[] computeLPS(String pattern) {
int m = [Link]();
int[] lps = new int[m];
int len = 0, i = 1;

while (i < m) {
if ([Link](i) == [Link](len)) {
lps[i++] = ++len;
} else {
 len = (len != 0) ? lps[len - 1] : 0;
if (len == 0) lps[i++] = 0;
}
}
return lps;
}

public static void KMP(String text, String pattern) {

int n = [Link](), m = [Link]();
int[] lps = computeLPS(pattern);

int i = 0, j = 0;
while (i < n) {
if ([Link](i) == [Link](j)) {
i++; j++;
}
if (j == m) {
[Link]("Pattern found at index " + (i - j));
j = lps[j - 1];
} else if (i < n && [Link](i) != [Link](j)) {
j = (j != 0) ? lps[j - 1] : i++;
}
}
}

public static void main(String[] args) {

String text = "ababcababcabc", pattern = "abc";
KMP(text, pattern);
}
}

Python Solution
def compute_lps(pattern):
m = len(pattern)
lps = [0] * m
length, i = 0, 1

while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps

def kmp(text, pattern):

n, m = len(text), len(pattern)
lps = compute_lps(pattern)

i, j = 0, 0
while i < n:
if text[i] == pattern[j]:
i, j = i + 1, j + 1
if j == m:
print(f"Pattern found at index {i - j}")
 j = lps[j - 1]
elif i < n and text[i] != pattern[j]:
j = lps[j - 1] if j != 0 else i + 1

# Example Usage
text, pattern = "ababcababcabc", "abc"
kmp(text, pattern)

📌 6. Implement the Rabin-Karp Algorithm for String Matching

Asked in: Adobe, Google, TCS

 Given a string S and a pattern P, implement Rabin-Karp algorithm to search for P in S using hashing.

C++ Solution
#include <bits/stdc++.h>
using namespace std;

#define PRIME 101 // A prime number for hashing

long long createHash(string str, int end) {

long long hash = 0;
for (int i = 0; i < end; i++)
hash = hash * PRIME + str[i];
return hash;
}

long long recalculateHash(string str, int oldIndex, int newIndex, long long
oldHash, int patternLength) {
oldHash -= str[oldIndex];
oldHash /= PRIME;
oldHash += str[newIndex] * pow(PRIME, patternLength - 1);
return oldHash;
}

void RabinKarp(string text, string pattern) {

int n = [Link](), m = [Link]();
long long patternHash = createHash(pattern, m);
long long textHash = createHash(text, m);

for (int i = 0; i <= n - m; i++) {

if (patternHash == textHash && [Link](i, m) == pattern)
cout << "Pattern found at index " << i << endl;

if (i < n - m)
textHash = recalculateHash(text, i, i + m, textHash, m);
}
}

int main() {
string text = "ababcabcabc", pattern = "abc";
RabinKarp(text, pattern);
return 0;
}
Java Solution
import [Link].*;

public class RabinKarpAlgorithm {

private static final int PRIME = 101; // Prime number for hashing

public static long createHash(String str, int end) {

long hash = 0;
for (int i = 0; i < end; i++)
hash = hash * PRIME + [Link](i);
return hash;
}

public static long recalculateHash(String str, int oldIndex, int

newIndex, long oldHash, int patternLength) {
oldHash -= [Link](oldIndex);
oldHash /= PRIME;
oldHash += [Link](newIndex) * [Link](PRIME, patternLength -
1);
return oldHash;
}

public static void rabinKarp(String text, String pattern) {

int n = [Link](), m = [Link]();
long patternHash = createHash(pattern, m);
long textHash = createHash(text, m);

for (int i = 0; i <= n - m; i++) {

if (patternHash == textHash && [Link](i, i +
m).equals(pattern))
[Link]("Pattern found at index " + i);

if (i < n - m)
textHash = recalculateHash(text, i, i + m, textHash, m);
}
}

public static void main(String[] args) {

String text = "ababcabcabc", pattern = "abc";
rabinKarp(text, pattern);
}
}

Python Solution
PRIME = 101 # Prime number for hashing

def create_hash(string, end):

hash_value = 0
for i in range(end):
hash_value = hash_value * PRIME + ord(string[i])
return hash_value

def recalculate_hash(string, old_index, new_index, old_hash,

pattern_length):
old_hash -= ord(string[old_index])
old_hash //= PRIME
old_hash += ord(string[new_index]) * (PRIME ** (pattern_length - 1))
return old_hash
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
pattern_hash = create_hash(pattern, m)
text_hash = create_hash(text, m)

for i in range(n - m + 1):

if pattern_hash == text_hash and text[i:i + m] == pattern:
print(f"Pattern found at index {i}")

if i < n - m:
text_hash = recalculate_hash(text, i, i + m, text_hash, m)

# Example Usage
text, pattern = "ababcabcabc", "abc"
rabin_karp(text, pattern)

📌 7. Find the Longest Common Prefix (LCP) Among Strings

Asked in: Microsoft, Google, Amazon

 Given an array of strings, find the longest common prefix among them.

C++ Solution (Horizontal Scanning)

#include <bits/stdc++.h>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {

if ([Link]()) return "";

string prefix = strs[0];

for (int i = 1; i < [Link](); i++) {
while (strs[i].find(prefix) != 0) {
prefix = [Link](0, [Link]() - 1);
if ([Link]()) return "";
}
}
return prefix;
}

int main() {
vector<string> strs = {"flower", "flow", "flight"};
cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << endl;
return 0;
}

Java Solution (Horizontal Scanning)

import [Link].*;

public class LCP {

public static String longestCommonPrefix(String[] strs) {
if ([Link] == 0) return "";

String prefix = strs[0];

for (int i = 1; i < [Link]; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = [Link](0, [Link]() - 1);
if ([Link]()) return "";
 }
}
return prefix;
}

public static void main(String[] args) {

String[] strs = {"flower", "flow", "flight"};
[Link]("Longest Common Prefix: " +
longestCommonPrefix(strs));
}
}

Python Solution (Horizontal Scanning)

def longest_common_prefix(strs):
if not strs:
return ""

prefix = strs[0]
for s in strs[1:]:
while not [Link](prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix

# Example Usage
strs = ["flower", "flow", "flight"]
print("Longest Common Prefix:", longest_common_prefix(strs))

📌 8. Find All Occurrences of a Pattern in a Text Using Z-Algorithm

Asked in: Flipkart, Amazon, TCS

 Given a text S and pattern P, use Z-Algorithm to efficiently find all occurrences of P in S.

C++ Solution
#include <bits/stdc++.h>
using namespace std;

// Function to compute the Z-array

vector<int> computeZ(string s) {
int n = [Link]();
vector<int> Z(n, 0);
int L = 0, R = 0;

for (int i = 1; i < n; i++) {

if (i <= R)
Z[i] = min(R - i + 1, Z[i - L]);

while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])

Z[i]++;

if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
 }
return Z;
}

// Function to find all occurrences of a pattern in a text using Z-

Algorithm
vector<int> findPattern(string text, string pattern) {
string combined = pattern + "$" + text;
vector<int> Z = computeZ(combined);
vector<int> occurrences;

int patternLength = [Link]();

for (int i = patternLength + 1; i < [Link](); i++) {
if (Z[i] == patternLength)
occurrences.push_back(i - patternLength - 1);
}
return occurrences;
}

int main() {
string text = "ababcababcab";
string pattern = "abc";

vector<int> result = findPattern(text, pattern);

for (int index : result)
cout << "Pattern found at index: " << index << endl;

return 0;
}

Java Solution
import [Link].*;

public class ZAlgorithm {

// Compute the Z-array
private static int[] computeZ(String s) {
int n = [Link]();
int[] Z = new int[n];
int L = 0, R = 0;

for (int i = 1; i < n; i++) {

if (i <= R)
Z[i] = [Link](R - i + 1, Z[i - L]);

while (i + Z[i] < n && [Link](Z[i]) == [Link](i + Z[i]))

Z[i]++;

if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
}
return Z;
}

// Find all occurrences of a pattern in a text using Z-Algorithm

public static List<Integer> findPattern(String text, String pattern) {
String combined = pattern + "$" + text;
int[] Z = computeZ(combined);
List<Integer> occurrences = new ArrayList<>();
 int patternLength = [Link]();
for (int i = patternLength + 1; i < [Link]; i++) {
if (Z[i] == patternLength)
[Link](i - patternLength - 1);
}
return occurrences;
}

public static void main(String[] args) {

String text = "ababcababcab";
String pattern = "abc";

List<Integer> result = findPattern(text, pattern);

for (int index : result)
[Link]("Pattern found at index: " + index);
}
}

Python Solution
def compute_z(s):
n = len(s)
Z = [0] * n
L, R = 0, 0

for i in range(1, n):

if i <= R:
Z[i] = min(R - i + 1, Z[i - L])

while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:

Z[i] += 1

if i + Z[i] - 1 > R:
L, R = i, i + Z[i] - 1

return Z

def find_pattern(text, pattern):

combined = pattern + "$" + text
Z = compute_z(combined)
pattern_length = len(pattern)
occurrences = []

for i in range(pattern_length + 1, len(Z)):

if Z[i] == pattern_length:
[Link](i - pattern_length - 1)

return occurrences

# Example usage
text = "ababcababcab"
pattern = "abc"
result = find_pattern(text, pattern)
for index in result:
print(f"Pattern found at index: {index}")
📌 9. Build a Suffix Array for a Given String
Asked in: Google, Microsoft, Amazon

 Construct a suffix array for a given string S, which helps in efficient pattern matching.

C++ Solution
#include <bits/stdc++.h>
using namespace std;

// Function to build a suffix array

vector<int> buildSuffixArray(const string &s) {
int n = [Link]();
vector<int> suffixArray(n), rank(n), tempRank(n);

// Initial ranking based on single characters

for (int i = 0; i < n; i++) {
suffixArray[i] = i;
rank[i] = s[i];
}

// Sort by doubling length (2^k)

for (int length = 1; length < n; length *= 2) {
auto cmp = [&](int a, int b) {
if (rank[a] != rank[b])
return rank[a] < rank[b];
int ra = (a + length < n) ? rank[a + length] : -1;
int rb = (b + length < n) ? rank[b + length] : -1;
return ra < rb;
};

sort([Link](), [Link](), cmp);

// Update ranks
tempRank[suffixArray[0]] = 0;
for (int i = 1; i < n; i++) {
tempRank[suffixArray[i]] = tempRank[suffixArray[i - 1]] +
cmp(suffixArray[i - 1], suffixArray[i]);
}
rank = tempRank;
}
return suffixArray;
}

// Driver Code
int main() {
string s = "banana";
vector<int> suffixArray = buildSuffixArray(s);

cout << "Suffix Array: ";

for (int i : suffixArray)
cout << i << " ";
cout << endl;

return 0;
}

Java Solution
import [Link].*;
public class SuffixArray {
// Function to build suffix array
public static int[] buildSuffixArray(String s) {
int n = [Link]();
Integer[] suffixArray = new Integer[n];
int[] rank = new int[n];
int[] tempRank = new int[n];

// Initial ranking based on single characters

for (int i = 0; i < n; i++) {
suffixArray[i] = i;
rank[i] = [Link](i);
}

// Sort suffixes by 2^k length

for (int length = 1; length < n; length *= 2) {
final int len = length;
[Link](suffixArray, (a, b) -> {
if (rank[a] != rank[b])
return [Link](rank[a], rank[b]);
int ra = (a + len < n) ? rank[a + len] : -1;
int rb = (b + len < n) ? rank[b + len] : -1;
return [Link](ra, rb);
});

// Update ranks
tempRank[suffixArray[0]] = 0;
for (int i = 1; i < n; i++) {
tempRank[suffixArray[i]] = tempRank[suffixArray[i - 1]] +
(rank[suffixArray[i - 1]] != rank[suffixArray[i]]
||
((suffixArray[i - 1] + length < n ?
rank[suffixArray[i - 1] + length] : -1) !=
(suffixArray[i] + length < n ? rank[suffixArray[i]
+ length] : -1)) ? 1 : 0);
}
rank = [Link](tempRank, n);
}

return
[Link](suffixArray).mapToInt(Integer::intValue).toArray();
}

// Driver Code
public static void main(String[] args) {
String s = "banana";
int[] suffixArray = buildSuffixArray(s);

[Link]("Suffix Array: ");

for (int index : suffixArray) {
[Link](index + " ");
}
}
}

Python Solution
def build_suffix_array(s):
n = len(s)
suffix_array = list(range(n))
rank = list(map(ord, s))
 temp_rank = [0] * n

# Sort suffixes by 2^k length

length = 1
while length < n:
suffix_array.sort(key=lambda i: (rank[i], rank[i + length] if i +
length < n else -1))

# Update ranks
temp_rank[suffix_array[0]] = 0
for i in range(1, n):
prev = suffix_array[i - 1]
curr = suffix_array[i]
temp_rank[curr] = temp_rank[prev] + (
rank[prev] != rank[curr] or
(rank[prev + length] if prev + length < n else -1) !=
(rank[curr + length] if curr + length < n else -1)
)
rank = temp_rank[:]
length *= 2

return suffix_array

# Example usage
s = "banana"
suffix_array = build_suffix_array(s)
print("Suffix Array:", suffix_array)

📌 10. Find the Longest Repeated Substring Using Suffix Arrays & LCP
Asked in: Google, Facebook, Microsoft

 Given a string S, find the longest repeated substring using suffix arrays and LCP (Longest Common
Prefix).

C++ Solution
#include <bits/stdc++.h>
using namespace std;

// Function to build a suffix array

vector<int> buildSuffixArray(const string &s) {
int n = [Link]();
vector<int> suffixArray(n), rank(n), tempRank(n);

// Initial ranking based on single characters

for (int i = 0; i < n; i++) {
suffixArray[i] = i;
rank[i] = s[i];
}

// Sort suffixes by doubling length (2^k)

for (int length = 1; length < n; length *= 2) {
auto cmp = [&](int a, int b) {
if (rank[a] != rank[b])
return rank[a] < rank[b];
int ra = (a + length < n) ? rank[a + length] : -1;
int rb = (b + length < n) ? rank[b + length] : -1;
return ra < rb;
 };

sort([Link](), [Link](), cmp);

// Update ranks
tempRank[suffixArray[0]] = 0;
for (int i = 1; i < n; i++) {
tempRank[suffixArray[i]] = tempRank[suffixArray[i - 1]] +
cmp(suffixArray[i - 1], suffixArray[i]);
}
rank = tempRank;
}
return suffixArray;
}

// Function to build the LCP (Longest Common Prefix) array

vector<int> buildLCPArray(const string &s, const vector<int> &suffixArray)
{
int n = [Link]();
vector<int> lcp(n, 0), rank(n, 0);

for (int i = 0; i < n; i++) {

rank[suffixArray[i]] = i;
}

int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] > 0) {
int j = suffixArray[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) h--;
}
}
return lcp;
}

// Function to find the longest repeated substring

string longestRepeatedSubstring(const string &s) {
vector<int> suffixArray = buildSuffixArray(s);
vector<int> lcp = buildLCPArray(s, suffixArray);

int maxLength = 0, index = 0;

for (int i = 1; i < [Link](); i++) {
if (lcp[i] > maxLength) {
maxLength = lcp[i];
index = suffixArray[i];
}
}

return [Link](index, maxLength);

}

// Driver Code
int main() {
string s = "banana";
string result = longestRepeatedSubstring(s);
cout << "Longest Repeated Substring: " << result << endl;
return 0;
}

Java Solution
import [Link].*;

public class LongestRepeatedSubstring {

// Function to build suffix array
public static int[] buildSuffixArray(String s) {
int n = [Link]();
Integer[] suffixArray = new Integer[n];
int[] rank = new int[n];
int[] tempRank = new int[n];

// Initial ranking based on single characters

for (int i = 0; i < n; i++) {
suffixArray[i] = i;
rank[i] = [Link](i);
}

// Sort suffixes by 2^k length

for (int length = 1; length < n; length *= 2) {
final int len = length;
[Link](suffixArray, (a, b) -> {
if (rank[a] != rank[b])
return [Link](rank[a], rank[b]);
int ra = (a + len < n) ? rank[a + len] : -1;
int rb = (b + len < n) ? rank[b + len] : -1;
return [Link](ra, rb);
});

// Update ranks
tempRank[suffixArray[0]] = 0;
for (int i = 1; i < n; i++) {
tempRank[suffixArray[i]] = tempRank[suffixArray[i - 1]] +
(rank[suffixArray[i - 1]] != rank[suffixArray[i]]
||
((suffixArray[i - 1] + length < n ?
rank[suffixArray[i - 1] + length] : -1) !=
(suffixArray[i] + length < n ? rank[suffixArray[i]
+ length] : -1)) ? 1 : 0);
}
rank = [Link](tempRank, n);
}

return
[Link](suffixArray).mapToInt(Integer::intValue).toArray();
}

// Function to find the longest repeated substring

public static String longestRepeatedSubstring(String s) {
int[] suffixArray = buildSuffixArray(s);
int n = [Link]();
int[] lcp = new int[n];
int[] rank = new int[n];

for (int i = 0; i < n; i++) {

rank[suffixArray[i]] = i;
}

int h = 0, maxLength = 0, index = 0;

 for (int i = 0; i < n; i++) {
if (rank[i] > 0) {
int j = suffixArray[rank[i] - 1];
while (i + h < n && j + h < n && [Link](i + h) ==
[Link](j + h)) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) h--;
if (lcp[rank[i]] > maxLength) {
maxLength = lcp[rank[i]];
index = suffixArray[rank[i]];
}
}
}
return [Link](index, index + maxLength);
}

// Driver Code
public static void main(String[] args) {
String s = "banana";
String result = longestRepeatedSubstring(s);
[Link]("Longest Repeated Substring: " + result);
}
}

Python Solution
def build_suffix_array(s):
n = len(s)
suffix_array = sorted(range(n), key=lambda i: s[i:])
return suffix_array

def build_lcp_array(s, suffix_array):

n = len(s)
rank = [0] * n
lcp = [0] * n

for i, suffix in enumerate(suffix_array):

rank[suffix] = i

h = 0
for i in range(n):
if rank[i] > 0:
j = suffix_array[rank[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rank[i]] = h
if h > 0:
h -= 1
return lcp

def longest_repeated_substring(s):
suffix_array = build_suffix_array(s)
lcp = build_lcp_array(s, suffix_array)
max_length = max(lcp)
index = [Link](max_length)
return s[suffix_array[index]:suffix_array[index] + max_length]

# Example usage
s = "banana"
print("Longest Repeated Substring:", longest_repeated_substring(s))

🎉 Congratulations! 🎉

You've successfully completed this PDF and taken one step closer to mastering coding
challenges! Your dedication and hard work will surely pay off. Keep pushing your limits and
sharpening your skills! 💻🔥

For more coding content, problem-solving techniques, and valuable insights, follow
@SYNTAX_ERROR on Instagram! 🚀📚

Keep coding, keep growing! 🚀🎯