How to Find a Randomly Inserted Character in a String in Python

Find the extra character inserted into a string by comparing original and modified strings

Understand the Problem

Problem Statement

Given two strings S and M, where S is the original string and M is formed by shuffling characters of S and inserting exactly one random character at any position. Your task is to find the randomly inserted character in string M.

Constraints

1 ≤ Length of S ≤ 1001
Length of M = Length of S + 1
Both strings contain only printable ASCII characters
Exactly one character in M is not present in S (when counting frequencies)

Examples

Example 1

Input

nelson
oneplsn

Output

Explanation

The original string 'nelson' has characters n, e, l, s, o. The modified string 'oneplsn' has all these characters plus an extra 'p'. When we count frequencies and decrement, 'p' will cause a negative count, identifying it as the inserted character.

Example 2

Input

AAaa
AaAaA

Output

Explanation

The original string 'AAaa' has 2 'A's and 2 'a's. The modified string 'AaAaA' has 3 'A's and 2 'a's. The extra 'A' will cause its count to go negative first, identifying it as the inserted character.

Solution

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

int main() {
    char s[1002], m[1003];
    int freq[256] = {0}; // ASCII character frequency array
    int i;
    
    // Read input strings
    fgets(s, sizeof(s), stdin);
    fgets(m, sizeof(m), stdin);
    
    // Remove newline characters
    s[strcspn(s, "\n")] = 0;
    m[strcspn(m, "\n")] = 0;
    
    // Count character frequencies in original string
    for (i = 0; s[i] != '\0'; i++) {
        freq[(unsigned char)s[i]]++;
    }
    
    // Find the extra character in modified string
    for (i = 0; m[i] != '\0'; i++) {
        freq[(unsigned char)m[i]]--;
        if (freq[(unsigned char)m[i]] < 0) {
            printf("%c\n", m[i]);
            return 0;
        }
    }
    
    return 0;
}

Time:O(n + m) where n is length of S and m is length of M. Since m = n + 1, this simplifies to O(n).

Space:O(1) - Uses a fixed-size array of 256 integers for ASCII character frequencies.

Approach:

Input Reading: Read both strings using fgets to handle spaces and newlines properly
Character Counting: Create a frequency array for ASCII characters and count occurrences in the original string
Character Matching: Iterate through the modified string, decrementing the frequency count for each character
Extra Character Detection: When a character's frequency goes negative, that character is the randomly inserted one
Output: Print the detected character and exit immediately

Visual Explanation

Loading diagram...

All Problems