Final string after performing given operations
Given a string str containing only characters x and y, the task is to perform the following operations while possible:
Find an index such that s[i] = ‘x’ and s[i+1] = ‘y’ and delete both the characters s[i] and s[i+1], if no such index is found then find an index such that s[i] = ‘y’ and s[i+1] = ‘x’ and swap(s[i], s[i+1]).
Print the final string after performing the given operation.
Examples:
Input: str = “xyyxx”
Output: x
Step 1: yxx (xy got deleted)
Step 2: xyx (yx got swapped)
Step 3: x (xy got deleted)Input: str = “xxyyxyy”
Output: y
Approach: In the final string there will be either only x or only y because if we have both x and y in the string then there would be a point where we have either xy or yx as sub-string.
- If it’s xy, we delete it straight away.
- If it is yx, we reverse it to get xy and then delete it.
Since in each deletion step, one x and one y gets deleted, the final string would have min(x, y) number of x and y characters deleted.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the modified string string printFinalString(string s) { int i, n; n = s.length(); int x = 0, y = 0; for (i = 0; i < n; i++) { // Count number of 'x' if (s[i] == 'x' ) x++; // Count number of 'y' else y++; } string finalString = "" ; // min(x, y) number of 'x' and 'y' will be deleted if (x > y) for (i = 0; i < x - y; i++) finalString += "x" ; else for (i = 0; i < y - x; i++) finalString += "y" ; return finalString; } // Driver Program to test above function int main() { string s = "xxyyxyy" ; cout << printFinalString(s); } |
Java
// Java implementation of the approach class GFG { // Function to return the modified String static String printFinalString(String s) { int i, n; n = s.length(); int x = 0 , y = 0 ; for (i = 0 ; i < n; i++) { // Count number of 'x' if (s.charAt(i) == 'x' ) { x++; } // Count number of 'y' else { y++; } } String finalString = "" ; // min(x, y) number of 'x' and // 'y' will be deleted if (x > y) { for (i = 0 ; i < x - y; i++) { finalString += "x" ; } } else { for (i = 0 ; i < y - x; i++) { finalString += "y" ; } } return finalString; } // Driver Code public static void main(String args[]) { String s = "xxyyxyy" ; System.out.println(printFinalString(s)); } } // This code is contributed // by 29AjayKumar |
Python3
# Python 3 implementation of the approach # Function to return the modified string def prFinalString(s): i, n = 0 , 0 n = len (s) x, y = 0 , 0 for i in range ( 0 , n): # Count number of 'x' if (s[i] = = 'x' ): x + = 1 # Count number of 'y' else : y + = 1 finalString = "" # min(x, y) number of 'x' and # 'y' will be deleted if (x > y): for i in range ( 0 , x - y): finalString + = "x" else : for i in range ( 0 , y - x): finalString + = "y" return finalString # Driver Code if __name__ = = '__main__' : s = "xxyyxyy" print (prFinalString(s)) # This code contributed by 29AjayKumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the modified String static string printFinalString( string s) { int i, n; n = s.Length; int x = 0, y = 0; for (i = 0; i < n; i++) { // Count number of 'x' if (s[i] == 'x' ) { x++; } // Count number of 'y' else { y++; } } string finalString = "" ; // min(x, y) number of 'x' and // 'y' will be deleted if (x > y) { for (i = 0; i < x - y; i++) { finalString += "x" ; } } else { for (i = 0; i < y - x; i++) { finalString += "y" ; } } return finalString; } // Driver Code public static void Main() { string s = "xxyyxyy" ; Console.WriteLine(printFinalString(s)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function to return the modified string function printFinalString( $s ) { $n = strlen ( $s ); $x = 0; $y = 0; for ( $i = 0; $i < $n ; $i ++) { // Count number of 'x' if ( $s [ $i ] == 'x' ) $x ++; // Count number of 'y' else $y ++; } $finalString = (string)null; // min(x, y) number of 'x' and 'y' will be deleted if ( $x > $y ) for ( $i = 0; $i < $x - $y ; $i ++) $finalString .= "x" ; else for ( $i = 0; $i < $y - $x ; $i ++) $finalString .= "y" ; return $finalString ; } // Driver Code $s = "xxyyxyy" ; echo printFinalString( $s ); // This code is contributed by ihritik ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the modified string function printFinalString(s) { var i, n; n = s.length; var x = 0, y = 0; for (i = 0; i < n; i++) { // Count number of 'x' if (s[i] == 'x' ) x++; // Count number of 'y' else y++; } var finalString = "" ; // min(x, y) number of 'x' and 'y' will be deleted if (x > y) for (i = 0; i < x - y; i++) finalString += "x" ; else for (i = 0; i < y - x; i++) finalString += "y" ; return finalString; } // Driver Program to test above function var s = "xxyyxyy" ; document.write( printFinalString(s)); // This code is contributed by famously. </script> |
y
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(n), where n is the length of the given string.
Contact Us