Added Character

Easy
0/40
Average time to solve is 10m
profile
Contributed by
24 upvotes
Asked in companies
Red HatCodenation

Problem statement

You are given a string 'S'. Now one more additional character is introduced in this string, which turns 'S' into new string 'T'. You have to find out this newly added character.

Note:

1. All the characters in string 'S' and 'T' consist of uppercase English alphabets.

2. Length of string 'T' is always 1 more than the length of string 'S'.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of the input contains an integer 'TEST' denoting the number of test cases.

The first line of each test case consists of a string 'S'.

The second line of each test consists of a string 'T'.
Output format: 
For each test case, print a character that denotes the newly added character in a new line.

Print the output for each test case in a separate line.
Note: 
You don't have to print anything, It has already been taken care of. Just Implement the given function.
Constraints: 
1 <= TEST <= 100
1 <= |S|, |T| <= 10^4

Where '|S|' and '|T|' denotes the length of he strings 'S' and 'T' respectively.

Time Limit: 1 sec.
Sample Input 1:
2
APPLE 
APPHLE
CODE
CODER
Sample Output 1:
H
R
Explanation for Sample Output 1:
In test case 1, As only character which is present in “APPHLE” but didn’t present in “APPLE” is ‘H’.

In test case 2, As only character which is present in “CODER” but didn’t present in “CODE" is ‘R’.
Sample Input 2:
2
MANGO 
MANNGO
NINJA
NIINJA
Sample Output 2:
N
I
Explanation for Sample Output 2:
In test case 1, As “MANGO” contains only 1 occurrence of ‘N’ but “MANNGO” contains 2 occurrences of ‘N’.

In test case 2, As “NINJA” contains only 1 occurrence of ‘I’ but “NIINJA" contains 2 occurrences of ‘I’.
Hint

Simply iterate through strings and compare.

Approaches (1)
Optimal Solution

Here in this algorithm we just need to check for the different character at the particular index. If all indexes has same character in both the strings then return the last character of the string ‘T’ as it is the added character in the string.

 

The steps are as follows:

 

  • Iterate through the elements of string ‘T’ (with loop variable ‘i’).
  • If ‘T[i]’ == ‘S[i]’, then move forward.
  • If ‘T[i]’ != ‘S[i]’, then we get the added element and return ‘T[i]’.
  • If ‘T[i]’ == ‘S[i]’, for all ‘i’ less than the length of string ‘S’, then the last character of string ‘T’ will be the required character.

 

Eg. In “APPLE” and “APPHLE”, starting from i=0 till i=2, all characters are the same, but at i=3 ‘L’ and ‘H’ are mismatching characters. Hence ‘H’ which is present in the second string is the added character. 

Time Complexity

O(N), Where ‘N’ is the length of the given string ‘S’.

 

Since we are iterating through the string ‘S’ once. Thus the timecomplexity will be O(N).

Space Complexity

O(1)

 

Since as we are using constant extra space. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Added Character
Full screen
Console