Encode The String

Easy
0/40
Average time to solve is 10m
profile
Contributed by
57 upvotes
Asked in companies
Goldman SachsDeloitteMahindra Comviva

Problem statement

You are given a string ‘S’ of length ‘N’. The string can be encoded using the following rules:

1) If the ‘i-th’ character is a vowel, change it to the next character in the alphabetical sequence. For example, the next character of ‘o’ is ‘p’.

2) If the ‘i-th’ character is a consonant, change it to the previous character in the alphabetical sequence. For example, the previous character of ‘h’ is ‘g’.

3) The next character of ‘z’ is ‘a’.

4) The previous character of ‘a’ is ‘z’.

Find the encoded string.

Example : 
‘N’ = 4, ‘S’ = “code”

Character ‘c’ gets changed to ‘b’.
Character ‘o’ gets changed to ‘p’.
Character ‘d’ gets changed to ‘c’.
Character ‘e’ gets changed to ‘f’.

Encoded string = “bpcf”
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’, denoting the length of the string.

The second line of each test case contains a string ‘S’ of length ‘N’.
Output Format : 
Print a string that denotes the encoded string of the original string.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <=  N <= 10^5

The Sum of ‘N’ over all test cases is <= 10^5.
The string ‘S’ contains only lowercase letters.

Time Limit: 1 sec
Sample Input 1 :
2
3
dog
4
cazz
Sample Output 1 :
cpf
bbyy
Explanation Of Sample Input 1 :
For the first test case :

Character ‘d’ gets changed to ‘c’.
Character ‘o’ gets changed to ‘p’.
Character ‘g’ gets changed to ‘f’.

Encoded string = “cpf”.


For the second test case :

Character ‘c’ gets changed to ‘b’.
Character ‘a’ gets changed to ‘b’.
Character ‘z’ gets changed to ‘y’.
Sample Input 2 :
2
4
gjmf
3
abc
Sample Output 2 :
file
bab
Hint

Simulate the problem statement.

Approaches (1)
Optimal Approach

 

Approach :

 

  • We will traverse the string from left to right, and for every character, we will check if it is a vowel and change it to the new character.
     
  • The vowels {‘a’, ‘e’, ‘i’, ‘o’, ‘u’} will get changed to {‘b’, ‘f’, ‘j’, ‘p’, ‘v’} respectively.

 

  • All the remaining alphabets ( i.e. consonants) will change to the previous characters in the alphabetical sequence.


 

Algorithm :
 

  • Loop through the string ‘S’ from ‘i’ = 1 to ‘i’ = ‘N’ :
    • If ( isVowel( ‘S[i]’ ) ) :
      • Change ‘S[i]’ to the next character.
    • Else :
      • Change ‘S[i]’ to the previous character.
  • Return ‘S’
Time Complexity

 

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

 

Since we are traversing the string once and the time to check if a character is a vowel is constant. So the overall Time Complexity is O(N).

Space Complexity

 

O(1)

 

We only need constant extra space here. So the total Space Complexity is constant, i.e. O(1).

Code Solution
(100% EXP penalty)
Encode The String
Full screen
Console