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

In this article, we will discuss how to identify a random character inserted into a string by comparing the original string and the modified string. The task involves sorting and comparing two strings: one being the original string and the other having one extra randomly inserted character.

---

Problem Description

Task:
Given two strings, S and M, where S represents the original name of a boy, and M is the modified name obtained by shuffling the characters of S and inserting one random character at any position. Your task is to find the randomly inserted character in string M.

Boundary Condition(s):

• 1 ≤ Length of S ≤ 1001

Input Format:

• The first line contains string S.
• The second line contains string M.

Output Format:

• The first line contains the randomly inserted character in M.

---

Example Input/Output

Example 1:

Input:

nelson
oneplsn

Output:

p

Explanation:
Here, string S = "nelson" and the modified string M = "oneplsn". By comparing both strings after sorting them, we can see that the character p is the randomly inserted character.

---

Example 2:

Input:

AAaa
AaAaA

Output:

A

Explanation:
In this case, the original string S = "AAaa" and the modified string M = "AaAaA". By sorting and comparing the strings, we find that the randomly inserted character is A.

---

Python Code to Solve the Problem

Below is a Python solution that finds the randomly inserted character by sorting both the original string S and the modified string M, and then comparing the sorted versions of both strings.

# Read input strings
string1 = sorted(input().strip())  # The original string S
string2 = sorted(input().strip())  # The modified string M

# Compare both strings
for ele in range(len(string1)):
    if string1[ele] != string2[ele]:  # Find the first differing character
        print(string2[ele])  # This is the randomly inserted character
        exit()

# If no difference is found in the first part, the extra character is the last one
print(string2[-1])

---

Explanation of the Code

1. Sorting the Strings:
   • We first sort both strings, S and M. Sorting helps because it organizes the characters in lexicographical order. After sorting, the order of characters in the modified string M will differ from S by exactly one character, which is the randomly inserted one.
2. Comparing the Sorted Strings:
   • We compare the characters of both sorted strings. If a mismatch is found at any position, it indicates that the character in the modified string M at that position is the randomly inserted character. This is printed as the result.
3. Handling the Case Where the Extra Character is at the End:
   • If no mismatch is found in the main part of the strings, then the extra character must be the last character in the modified string M. We print this character.
4. Exit After Finding the Character:
   • Once the extra character is found, the program exits, ensuring efficient execution.

---

Step-by-Step Example Walkthrough

Example 1:

Input:

nelson
oneplsn

Steps:

1. Sort the original string S = "nelson", resulting in ['e', 'l', 'n', 'o', 's'].
2. Sort the modified string M = "oneplsn", resulting in ['e', 'l', 'n', 'o', 'p', 's'].
3. Compare the sorted versions of both strings. At the fourth position, we notice that the character p in M does not appear in S.
4. The output is p.

---

Example 2:

Input:

AAaa
AaAaA

Steps:

1. Sort the original string S = "AAaa", resulting in ['A', 'A', 'a', 'a'].
2. Sort the modified string M = "AaAaA", resulting in ['A', 'A', 'A', 'a', 'a'].
3. Compare the sorted versions of both strings. At the third position, we notice that the character A in M is the randomly inserted character.
4. The output is A.

---

Conclusion

This Python program efficiently identifies the randomly inserted character in a string by utilizing sorting and string comparison techniques. It works for any input size within the given boundary conditions and demonstrates an excellent use case for string manipulation in Python. This approach ensures that the program runs efficiently and produces correct results even for larger strings.

By understanding the logic behind sorting and comparing strings, one can adapt this solution for other similar string manipulation problems as well.