Reformat The String Leetcode Solution

Difficulty Level Easy
Frequently asked in Microsoft
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 2423

Problem Statement

In this problem, we are given an alphanumeric string i.e. the string has only lowercase alphabets (a-z) and digits(0-9). We are required to return any permutation of this string, in which there is no consecutive alphabet in it or no consecutive digits. If no such permutation is there, then we have to return an empty string.

Example

s = "a0b1c2"
"0a1b2c"

Explanation:

No two adjacent characters have the same type in “0a1b2c”.
“a0b1c2”, “0a1b2c”, “0c2a1b” are also valid permutations.

s = "leetcode"
""

Explanation:

“leetcode” has only characters so we cannot separate them by digits.

Approach

Let’s first understand the condition in which we can return a permutation.
Suppose if string is “abcde” then we can’t make any possible permutation from it in which no two alphabets or numbers are consecutive.
Similarly if string is “12335” then also we can’t do anything.
So, to make alternative alphanumeric string, should we have equal number of digits and alphabets?
No, Let’s see example “covid2019” we have 5 alphabets and 4 digits.
Still we have possible ans e.g. “c2o0v1i9d”.

Reformat The String Leetcode Solution

Now if there would be one more alphabet in the same string, let “covids2019” then also we could not form any possible output.
Thus here we have got a condition that difference of count of alphabets and count of digits should not exceed 1.
i.e. abs(count(digits)-count(alphabets))<=1, other wise no output possible.

Let’s understand the algorithm now,

Algorithm

  1. To create the alternative output, we should do grouping alphabets and digits separately.
  2. After that we can check the size of both groups, if the difference exceeds 1 we returnempty string. Else we go further.
  3. We can now check size of both group,
    if size of a group (group of alphabets) is larger (by one) than another (group of digits), then we have to start by filling a character of larger group at first place in output string.
    Otherwise, any group’s character may take first place.
    Here we are using a flag variable for this task. Which is nothing but a turn for both group. If the flag is true, then we move further by putting alphabet at current place in output string. Otherwise, we will put a digit.
    Also on each fill, we will invert flag to keep alternation between the two groups.
  4. So, before we appending the characters one by one in output, we will keep our flag true if alphabet group are larger in size, else flag will remain false.
  5. Now this is output string and we have to return the same.

Implementation

C++ Program for Reformat The String Leetcode Solution

#include <iostream>
using namespace std;

string reformat(string s) {
        
        string alphas;
        string digs;
        
        for(int i=0;i<s.length();i++){
            char ch=s[i];
            string str=string(1, ch); 
            if(ch>='0' && ch<='9')digs.append(str);
            else alphas.append(str);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=abs(alen-dlen);
        if(diff>1)return "";
        
        string ans;
        
        bool flag=0;
        if(alen-dlen==1)flag=1;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                string str=string(1, alphas[j++]); 
                ans.append(str);
            }else{
                string str=string(1, digs[k++]); 
                ans.append(str);
            }
            flag=!flag;
        }
    
        return ans;
    }


int main() {
  string str="covid2019";
  string ans=reformat(str);
    cout<<ans<<endl;	
  return 0;
}
c2o0v1i9d

Java Program for Reformat The String Leetcode Solution

import java.util.*;
class ReformatString{
  public static  String reformat(String s) {
        
        StringBuilder alphas=new StringBuilder();
        StringBuilder digs=new StringBuilder();
        
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch>='0' && ch<='9')digs.append(ch);
            else alphas.append(ch);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=Math.abs(alen-dlen);
        if(diff>1)return "";
        
        StringBuilder ans=new StringBuilder();
        
        boolean flag=false;
        if(alen-dlen==1)flag=true;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                ans.append(alphas.charAt(j++));
            }else{
                ans.append(digs.charAt(k++));
            }
            flag=!flag;
        }
        return ans.toString();
    }
  
    public static void main(String args[]){
        
    String str="covid2019";
    String ans=reformat(str);
    System.out.println(ans);
    }
}
c2o0v1i9d

Complexity Analysis for Reformat The String Leetcode Solution

Time Complexity

O(n) : Because, we are working linearly on the input string. Hence, the time complexity will be O(n).

Space Complexity 

O(n) : We have to use few extra strings :

  • a. for alphabet group
  • b. for digits group
  • c. for output

Size of all of these are at most the length of input string
Hence, the space complexity too is O(n).

Translate »