Licence Key Formatting Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/license-key-formatting/1
(It is also the problem of the day for 21-09-2022)
Solution:
class Solution{
static String ReFormatString(String s, int k){
StringBuilder sb=new StringBuilder(s);
StringBuilder sb2=new StringBuilder();
for(int i=0;i<sb.length();i++){
if(sb.charAt(i)!='-'){
sb.setCharAt(i,Character.toUpperCase(sb.charAt(i)));
sb2.append(Character.toUpperCase(s.charAt(i)));
}
}
if(sb.length()<k){
return sb2.toString();
}
StringBuilder sb1=new StringBuilder();
int count=0;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)!='-'){
if(count==k){
count=01;
sb1.append("-");
sb1.append(sb.charAt(i));
}
else{
count++;
sb1.append(sb.charAt(i));
}
}
}
sb1.reverse();
return sb1.toString();
}
}
Time Complexity: O(S)[S=String Length]
Space Complexity: O(S)[String is used]
Auxiliary Space: O(S)[New String or StringBuilder of that size will be created]
[If we say we are iterating a string of size S(S=string.length()) then time complexity is O(s), however, the same logic is we are also creating a string or StringBuilder of size nearly equal to S then auxiliary space should be O(S).
So according to the question and our solution if
time complexity is O(S) then
space complexity or auxiliary space should be O(S).]
Approach Explained:
1. We want all characters in our output string as the upper case so why not convert the whole string to the upper case in the start only.
2. We can leave the first group with a size less than k, however, all other groups should have a size equivalent to k so it means we need to traverse from the end.
3. While traversing from the end we need to maintain a check on the count of characters in one group, if they are equal to k then we will add '-' in the string and change the count value.
4.No need of considering '-' in the traversal as they are donating only the number of groups.
So workflow:
1. Make StringBuilder objects, sb containing full string s input by the user, sb2 an empty buffer, and sb1 and empty buffer too.
2. Traverse the given string from last and while traversing ignore the '-' character.
3. While traversing keep on adding the character in sb2 first and later check, whether its size is more than k or less than k.
if it's less than k return an answer. eg s="bS-" and k=4 so sb2="BS" and k=4 so sb2.length()<k return sb2.toString()
else:
Now traverse again from last and keep the focus on characters other than '-'. Simultaneously maintain a count of characters inserted in the sb.
if count==k then it means the group got complete, so add on the '-' character.
else incrementing the count value and keep on adding the character.
Note:
The point here is if count==k then I have written count=1 and append '-' and character at that index too, its so because eg
s=GrdE-cTFr
sb=GRDE-CTFR
k=4
then sb1="" count=0
Traversal from last:
sb1="R" count=1
sb1="RF" count=2
sb1="RFT" count=3
sb1="RFTC" count=4 ie k
ignore character '-'
now the next character is 'E' and while count=k so now it will go inside if condition and
count=1 sb1="RFTC-" and later sb1="RFTC-E"
(Here count=1 indicates that this character is not '-' and it will be appended in the string also, but before its arrival its previous group got full so it means it will start a new group and since it will be the first member of that group it will make count as 1.)
Later reversing sb1 as we are traversing from the opposite direction and we want an answer from the forwarding direction so reversing the final StringBuilder sb1 and returning it into the form of string.
"Thanks for Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment