Home » Technical Interview Questions » String Interview Questions » Longest Common Extension

Longest Common Extension


Given a string s and some of the pairs (L,R), write a function that will output the length of the longest sub string starting at L and R

Example

INPUT

s = “abcbabcb”

Queries : (1,3), (1,5), (0,1)

OUTPUT

1, for (1,3) starting at index 1 we have ‘b’ and at index 3 also we have ‘b’, but other characters dont match 3 for (1,5) starting at index 1 we have “bcb” and at index 5 we have “bcb” 0 for (0,1) charcters dont match

Algorithm

For each LCE query

1. Initialize length to 0

2. start comparing the characters starting from the indexes L and R

3. If the characters match, then this character is in Longest Common Extension so increament length

4. Else, if the characters mismatch then return the length

C++ Program

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

//function to find LCE
int LCE(string str, int n, int L, int R)
{
    int length = 0;
    //till characters dont match
    while (str[L+length] == str[R+length] &&
            R+length < n)
        length++;

    return(length);
}


int main()
{
    int L = 1;
    int R = 5;
    string str = "abcbabcb";
    int n = str.length();


    cout<<LCE(str, n, L, R);

    return (0);
}

Try It

 

READ  Reverse individual words
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup