medium
0 views

Remove Characters from Left

Find the minimum number of characters to remove from the left side of two strings so that the remaining parts become equal (case-insensitive).

Understand the Problem

Problem Statement

Remove Characters from Left: The program must accept two string values S1 and S2 as the input. The program must print the minimum number of characters M to be removed from the left side of the given string values so that the revised string values become equal (ignoring the case). If it is not possible, then the program must print -1 as the output.

Constraints

  • 1 ≤ Length of S1 ≤ 1000
  • 1 ≤ Length of S2 ≤ 1000
  • Strings can contain letters (a-z, A-Z), digits (0-9), and special characters
  • Comparison should be case-insensitive
  • If no common suffix exists, output -1

Examples

Example 1
Input
Cream
JAM
Output
4
Explanation

After removing the first 3 characters from 'Cream', it becomes 'am'. After removing the first character from 'JAM', it becomes 'AM'. The revised strings 'am' and 'AM' are equal ignoring case. Total characters removed = 3 + 1 = 4.

Example 2
Input
corn
Corn
Output
0
Explanation

The strings 'corn' and 'Corn' are already equal when ignoring case, so no characters need to be removed.

Example 3
Input
123@abc
123@XYZ
Output
-1
Explanation

After removing the common prefix '123@', we get 'abc' and 'XYZ' which have no common suffix. Since there's no way to make them equal by only removing characters from the left, the output is -1.

Solution

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char S1[1001], S2[1001];
    char rev1[1001], rev2[1001];
    
    // Read input strings
    fgets(S1, sizeof(S1), stdin);
    fgets(S2, sizeof(S2), stdin);
    
    // Remove newline characters
    S1[strcspn(S1, "\n")] = 0;
    S2[strcspn(S2, "\n")] = 0;
    
    int len1 = strlen(S1);
    int len2 = strlen(S2);
    
    // Convert to lowercase
    for (int i = 0; i < len1; i++) {
        S1[i] = tolower(S1[i]);
    }
    for (int i = 0; i < len2; i++) {
        S2[i] = tolower(S2[i]);
    }
    
    // Reverse strings to work from end
    for (int i = 0; i < len1; i++) {
        rev1[i] = S1[len1 - 1 - i];
    }
    rev1[len1] = '\0';
    
    for (int i = 0; i < len2; i++) {
        rev2[i] = S2[len2 - 1 - i];
    }
    rev2[len2] = '\0';
    
    // Find longest common suffix
    int common_length = 0;
    int min_len = (len1 < len2) ? len1 : len2;
    
    for (int i = 0; i < min_len; i++) {
        if (rev1[i] == rev2[i]) {
            common_length++;
        } else {
            break;
        }
    }
    
    // Handle edge cases
    if (common_length == 0) {
        printf("-1\n");
    } else if (strcmp(S1, S2) == 0) {
        printf("0\n");
    } else {
        int chars_to_remove = (len1 - common_length) + (len2 - common_length);
        printf("%d\n", chars_to_remove);
    }
    
    return 0;
}
Time:O(n) where n is the maximum length of the two strings
Space:O(n) for storing the reversed strings
Approach:

C Solution Explanation:

  1. Read both input strings using fgets() and remove trailing newlines
  2. Convert both strings to lowercase using tolower() for case-insensitive comparison
  3. Reverse both strings by copying characters from end to beginning
  4. Find the longest common suffix by comparing characters from the start of the reversed strings
  5. Calculate total characters to remove: (length1 - common_suffix_length) + (length2 - common_suffix_length)
  6. Handle special cases: no common suffix (-1) or already equal strings (0)

The time complexity is O(n) where n is the maximum string length, and space complexity is O(n) for storing the reversed strings.

Visual Explanation

Loading diagram...
All Problems