Encode The String
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”

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

Question

Encode The String

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”

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

Accepted Answer

a) Pick the first character from the source string.
b) Append the picked character to the destination string.
c) Count the number of subsequent occurrences of the picked character and append the count to the destination string.
d) Pick the next character and repeat steps b) c) and d) if the end of the string is NOT reached.

Accepted Answer

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’

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(1)



    where 'N' is the length of the given string.

'''



from typing import *



# Return true if character 'x' is vowel.



def isVowel(x) :

	return (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u')





def encodeString(s: str, n: int) :

	

	s = list(s)

    # Traverse the string.

	for i in range(n) :

		

		# Check if 'i-th' character is vowel.

		if(isVowel(s[i])) :

			s[i] = chr(ord(s[i]) + 1)	# Next character if vowel.

		

		else :

			s[i] = chr(ord(s[i]) - 1)	# Previous character if consonant.

		

	# Return the encoded string.

	return "".join(s)

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where 'N' is the length of the string 'S'.

 */



class Solution {



  // Return true if character 'x' is vowel.

  static boolean isVowel(char x) {

    return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u');

  }



  public static String encodeString(int n, String s) {



    String t = "";



    // Traverse the string.

    for (int i = 0; i < n; ++i) {

      int x;

      // Check if 'i-th' character is vowel.

      if (isVowel(s.charAt(i))) {

        // Next character if vowel.

        x = s.charAt(i) + 1;

      } else {

        // Previous character if consonant.

        x = s.charAt(i) - 1;

      }

      // Add encoded character to final result.

      t += (char) x;

    }



    // Return the encoded string.

    return t;

  }

}

C++ (g++ 5.4)

/*
    Time complexity: O(N)
    Space complexity: O(1)

    where 'N' is the length of the given string.
*/

// Return true if character 'x' is vowel.
bool isVowel(char x) {
	return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u');
}

string encodeString(string &s, int n) {
	
	// Traverse the string.
	for(int i = 0; i < n; ++i) {
		
		// Check if 'i-th' character is vowel.
		if(isVowel(s[i])) {
			s[i] = char(s[i] + 1);	// Next character if vowel.
		}
		else {
			s[i] = char(s[i] - 1);	// Previous character if consonant.
		}
	}
	
	// Return the encoded string.
	return s;
}

Accepted Answer

Encode The String

You are given a password string P of length N. The password needs to be encoded before storing it to the database. The password string can be encoded using the following rules:

1) If the k-th character is a vowel, change it to the second next character in the alphabetical sequence. For example, the second next character of o is q. HAT

2) If the k-th character is a consonant, change it to the second previous character in the alphabetical sequence. For example, the second previous character of his f.

Display the encoded password string.