Check if a string is a double string | Letuscode

Check if a string is a double string | Letuscode
Given a string, we need to check if a string is a double string possibly by deleting a character.
A double string is a repetition of two strings affixed together.
For example the following strings are double strings
"aa", "meme", "abbabb"
Where as the follwing are not double strings
"ab", "abc", "acbab"
However "acbab" can be be a double string if we remove "c" from it.

Case 1:
If the given string is of even length, we simply need to check if it is a double string by checking if the left half and right half are equal.
No need to consider the case of deleting a character because, if we delete a character, it’s length will be odd which will never be a double string.

Case 2:
If the string is of odd length, we have to delete a character before checking if it is a double string. How to find out which character to be deleted?

So it appears that we should try to remove each possible character and check if it is a double string. However since we want to check for a double string,
the left and right half should atleast be similar if not equal.

Consider an example “acbab”, we can divide the string into longer and shorter halves in two ways
("acb", "ab")
("ac", "bab")
Since the first pair of string differ by only character (In other words, their edit distance is just 1)

So we just need to check if the edit distance between the longer and shorter strings is at most 1.

bool is_double(string &input) {
    size_t len = input.size();
    if( len % 2 == 1 )
        return false;
    int i;
    int mid = len/2;
    for( i = 0; i < mid; i++ ) {
        if( input[i] != input[i+mid] )
            return false;
    }
    return true;
}

bool is_sub_seq(string &longer, string &shorter) {
    int i, j;
    bool mismatch = false;
    for( i = 0, j = 0; i < longer.size() && j < shorter.size(); ) {
        if( longer[i] != shorter[j] ) {
            if( mismatch ) {
                return false;//more than one mismatch; not a double string
            }
            else {
                mismatch = true; //one mismatch is fine
                i++; //skip this character from the longer half
            }
        }
        else
        {
            i++;
            j++;
        }
    }
    return true;
}

bool can_be_double(string &input) {
    size_t len = input.size();
    if( len < 2 )
        return false;
    if( len % 2 == 0 )
        return is_double(input);
    else
    {
        string longer = input.substr(0, len/2+1);
        string shorter = input.substr(len/2+1, len/2);
        if( is_sub_seq(longer, shorter) )
            return true;
        shorter = input.substr(0, len/2);
        longer = input.substr(len/2, len/2+1);
        return is_sub_seq(longer,shorter);
    }
}
Read full article from Check if a string is a double string | Letuscode