[SOLVED] I have made recurrence relation which finds the longest contiguous common string between two strings how can i skip one char in my one of the string

Issue

int lcs(int i, int j, int count) 
{ 
    
    if (i == 0 || j == 0) 
        return count; 
        
    if (X[i-1] == Y[j-1]) { 
        count = lcs(i - 1, j - 1, count + 1); 
    } 
      
        count = max(count, max(lcs( i, j - 1, 0), lcs( i - 1, j, 0))); 
    return count; 
} 

For example: The X contains AABB and Y contains AACB i want my recurrence relation to skip c to give AAB as the lCCS, this is what i have done so far.

Solution

Assuming you use std::string, you can remove a character from a string via its erase:

std::string A{"AACB"};
std::string copy = A;  // make a copy to keep the original
copy.erase(2);         // erase character at pos 2
std::cout << copy;     // prints AAB

If you don't know which character to remove in advance, you can try all characters in a loop and call your function for X and the other string Y after removing one character, in a loop.

Answered By - 463035818_is_not_a_number