Amazon Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
Will it maintain order of the string ? I checked online but not sure if that actually maintains order .
After this is done we need to regroup the 3 different groups in the order of the input array to keep the order.
This is my solution to the problem.
public class AlphabetSorter {
public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";
for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}
return lowers + spaces + uppers;
}
public static void main(String []args) {
String output = AlphabetSorter.sortString("a cBd LkmY");
System.out.println(output); //result: acdkm BLY
}
}
you are using extra space with 3 string reference (lowers, psace, uppers) and many String instance
Used selection sort with a custom comparison logic which resides in the IsSpecialSmaller method.
These are my extension methods for the char.
public static class CharExtensions
{
public static bool IsSmall(this char c)
{
return c >= 97 && c <= 122;
}
public static bool IsSpace(this char c)
{
return c == 32;
}
public static bool IsUpper(this char c)
{
return c >= 65 && c <= 90;
}
}
And then the solution that uses these extension methods:
public static void Sort(char[] str)
{
for (int i = 0; i < str.Length; i++)
{
var minIndex = i;
for (int j = i + 1; j < str.Length; j++)
{
if (IsSpecialSmaller(str[j], str[minIndex]))
{
minIndex = j;
}
}
SwapChars(str, i, minIndex);
}
}
private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper() || a < b;
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return b.IsUpper() ? a < b : false;
}
}
private static void SwapChars(char[] str, int i, int j)
{
var tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
I've noticed that the question is demanding that the original order among groups need to stay the same whereas my above code sorts them too. So the updated version of IsSpecialSmaller() method will avoid that.
private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper();
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return false;
}
}
It is indeed O(n^2) for runtime. Your comment made me realize O(n) is requested so mine wouldn't be the correct answer.
char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}
private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}
private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}
private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}
public static String arrange(String input) {
char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}
private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}
private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}
private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}
public class ArrangeCharacters {
public static String arrange(String input) {
char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}
private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}
private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}
private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}
private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}
}
Actually, it is like a insertion sort. Compare each element i to 0 backwards.
Convert string to char array to each exchange and compare operation.
There are 3 conditions in which 2nd loops runs and exchange elements:
1) when in string Ul (U is upper case, l is lower case)
2) when Sl (s is space)
3) when US
Break condition is when : ll and above 3 condition not satisfied
This will give not exact o(n) but almost n as 2nd loops run only above 3 cases.
It is easy. It can be done in two iterations of the array.
iteration 1)- start from the left side of the array find the first space. then find the small case letter after finding the space and swap. continue this till no small case letters found after space.
iterations 2) - Start from right side of the array but with capital case and spaces.
Now repeat again iteration 1) - After this entire array would be partitioned as small case, spaces and Upper case with maintaing the order.
This solution is O(n) for swaps and O(n**2) on compares (and requires at least one space to do anything):
package me.arranger;
import java.util.ArrayList;
public class InplaceArranger
{
public static void Rearrange(char[ ] Letters)
{
LeftToRight(Letters);
RightToLeft(Letters);
LeftToRight(Letters);
}
private static void Swap(char[ ] Letters, int left, int right)
{
if ((left < Letters.length) && (right < Letters.length))
{
char hold = Letters[left];
Letters[left] = Letters[right];
Letters[right] = hold;
}
}
private static void LeftToRight(char[ ] Letters)
{
int iPos;
for (iPos = 0; iPos < Letters.length; iPos ++)
{
if (Letters[iPos] == ' ')
{
int iLower;
// Swap this space with the first lower-case character after it.
for (iLower = iPos + 1; ((iLower < Letters.length) && ( ! Character.isLowerCase(Letters[iLower]))); iLower ++)
;
if (iLower < Letters.length) Swap(Letters, iPos, iLower);
}
}
}
private static void RightToLeft(char[ ] Letters)
{
int iPos;
if (Letters.length == 0) return;
for (iPos = (Letters.length - 1); iPos >= 0; iPos --)
{
if (Letters[iPos] == ' ')
{
int iUpper;
// Swap this space with the first upper-case character before it.
for (iUpper = iPos - 1; ((iUpper >= 0) && ( ! Character.isUpperCase(Letters[iUpper]))); iUpper --)
;
if (iUpper >= 0) Swap(Letters, iUpper, iPos);
}
}
}
public static void main(String[] args)
{
String Text = "ab CDe fGHi JK lm";
char[ ] TextArray = Text.toCharArray( );
System.out.println(Text);
Rearrange(TextArray);
Text = new String(TextArray);
System.out.println(Text);
}
}
The problem states that the string will contain spaces. I think this is the correct solution. I don't think there is a possible solution without at least one space.
I don't think this is a correct algorithm. The existence of space is not a problem, we can solve it by metamorphosing-and-restoring method.
This algorithm claims iteration1->iteration2->iteration1.
Suppose we have a string 5ABcd, where 5 represents space.
Iteration 1: after the 1st swap, cAB5d; after the 2nd swap, cABd5.
Iteration 2: after the 1st swap, cA5dB; after the 2nd swap, c5AdB.
Iteration 1: after the 1st swap, cdA5B.
The result is incorrect. Of course we can perform iteration 2 again. But this is only for a simple example. For longer and more complex string, the repeat times will increase.
Actually, I suspect if there exists a O(n) time O(1) space algorithm
What about this...?
public class AlphabetSorter {
public static void sortString(String input) {
for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
System.out.print(input.charAt(i));
}
}
for (int i = 0; i < input.length(); ++i) {
if (Character.isUpperCase(input.charAt(i))) {
System.out.print(input.charAt(i));
}
}
for (int i = 0; i < input.length(); ++i) {
if (input.charAt(i) == ' ') {
System.out.print(input.charAt(i));
}
}
}
public static void main(String []args) {
AlphabetSorter.sortString("a cBd LkmY");
}
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
char *str = "Got it Working Man";
char *temp_capital = (char*)malloc(sizeof(strlen(str)));
char *temp_small = (char*)malloc(sizeof(strlen(str)));
int length_capital = 0;
int length_small = 0;
while(*str != '\0')
{
if(*str != ' ')
{
if( (*str >= 'A') && (*str <= 'Z') )
{
*temp_capital++ = *str;
length_capital++;
}
else if( (*str >= 'a') && (*str <= 'z') )
{
*temp_small++ = *str;
length_small++;
}
}
else
{
}
str++;
}
*temp_capital = '\0';
*temp_small++ = ' ';
*temp_small = '\0';
temp_capital = temp_capital - length_capital;
temp_small = (temp_small - (length_small+1));
printf(" The list of capital :%s \n", temp_capital );
printf(" The list of small :%s \n", temp_small );
printf("The concatenated string: %s", strcat(temp_small, temp_capital));
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
char *str = "Got it Working Man";
char *temp_capital = (char*)malloc(sizeof(strlen(str)));
char *temp_small = (char*)malloc(sizeof(strlen(str)));
int length_capital = 0;
int length_small = 0;
while(*str != '\0')
{
if(*str != ' ')
{
if( (*str >= 'A') && (*str <= 'Z') )
{
*temp_capital++ = *str;
length_capital++;
}
else if( (*str >= 'a') && (*str <= 'z') )
{
*temp_small++ = *str;
length_small++;
}
}
else
{
}
str++;
}
*temp_capital = '\0';
*temp_small++ = ' ';
*temp_small = '\0';
temp_capital = temp_capital - length_capital;
temp_small = (temp_small - (length_small+1));
printf(" The list of capital :%s \n", temp_capital );
printf(" The list of small :%s \n", temp_small );
printf("The concatenated string: %s", strcat(temp_small, temp_capital));
return 0;
}
Here is C# example
/// <summary>
/// Arrange String LowerCase Space Upper Case
/// </summary>
/// <param name="Input"></param>
/// <returns></returns>
public static string ArrangeStringLowSpaceUpper(string Input)
{
StringBuilder sb = new StringBuilder();
foreach (char c in Input)
{
if (Convert.ToInt32('a') <= Convert.ToInt32(c) && Convert.ToInt32('z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
sb.Append(' ');
foreach (char c in Input)
{
if (Convert.ToInt32('A') <= Convert.ToInt32(c) && Convert.ToInt32('Z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
return sb.ToString();
}
/// <summary>
/// Arrange String LowerCase Space Upper Case
/// </summary>
/// <param name="Input"></param>
/// <returns></returns>
public static string ArrangeStringLowSpaceUpper(string Input)
{
StringBuilder sb = new StringBuilder();
foreach (char c in Input)
{
if (Convert.ToInt32('a') <= Convert.ToInt32(c) && Convert.ToInt32('z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
sb.Append(' ');
foreach (char c in Input)
{
if (Convert.ToInt32('A') <= Convert.ToInt32(c) && Convert.ToInt32('Z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
return sb.ToString();
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortChar {
public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();
String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
space.add(s.charAt(i));
} else if (ascci >= 65 && ascci <= 90) {
uppercase.add(s.charAt(i)) ;
} else if(ascci >= 97 && ascci <= 122) {
lower.add(s.charAt(i));
}
}
Collections.sort(uppercase);
Collections.sort(lower);
for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}
System.out.println(str);
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortChar {
public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();
String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
space.add(s.charAt(i));
} else if (ascci >= 65 && ascci <= 90) {
uppercase.add(s.charAt(i)) ;
} else if(ascci >= 97 && ascci <= 122) {
lower.add(s.charAt(i));
}
}
Collections.sort(uppercase);
Collections.sort(lower);
for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}
System.out.println(str);
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortChar {
public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();
String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
space.add(s.charAt(i));
} else if (ascci >= 65 && ascci <= 90) {
uppercase.add(s.charAt(i)) ;
} else if(ascci >= 97 && ascci <= 122) {
lower.add(s.charAt(i));
}
}
Collections.sort(uppercase);
Collections.sort(lower);
for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}
System.out.println(str);
}
}
public class SortChar {
public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();
String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
space.add(s.charAt(i));
} else if (ascci >= 65 && ascci <= 90) {
uppercase.add(s.charAt(i)) ;
} else if(ascci >= 97 && ascci <= 122) {
lower.add(s.charAt(i));
}
}
Collections.sort(uppercase);
Collections.sort(lower);
for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}
System.out.println(str);
}
}
public class SortChar {
public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();
String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
space.add(s.charAt(i));
} else if (ascci >= 65 && ascci <= 90) {
uppercase.add(s.charAt(i)) ;
} else if(ascci >= 97 && ascci <= 122) {
lower.add(s.charAt(i));
}
}
Collections.sort(uppercase);
Collections.sort(lower);
for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}
System.out.println(str);
}
}
Below code solve the problem in O(n)
package com.timepass.sortingx;
public class StringSort {
public static void threeWaySort(StringBuilder str){
int pos=0;
for (int i = pos; i < str.length(); i++) {
if(isLower(str.charAt(i))){
swap(str, pos++, i);
}
}
for (int i = pos; i < str.length(); i++) {
if(isSpace(str.charAt(i))){
swap(str, pos++, i);
}
}
for (int i = pos; i < str.length(); i++) {
if(isUpper(str.charAt(i))){
swap(str, pos++, i);
}
}
}
private static boolean isSpace(char ch){
return 32==ch;
}
private static boolean isUpper(char ch){
return ch>=65 && ch<=90;
}
private static boolean isLower(char ch){
return ch>=97 && ch<=122;
}
private static void swap(StringBuilder sb, int x, int y){
char y_char = sb.charAt(y);
sb.setCharAt(y, sb.charAt(x));
sb.setCharAt(x, y_char);
}
public static void main(String[] args) {
StringBuilder str = new StringBuilder("a cBd LkmY");
threeWaySort(str);
System.out.println(str);
}
}
You solved the problem in O(n) with no extra memory. However, you only keep the order of lower case letters. Imagine the bellow test case:
1. "aBDEFc"
You your program you will get:
After 1st loop (swap all lower case to begin):"acDEFB" (swipe 'c' with 'B')
No changes in spaces loop.
After 3rd loop, you will keep the same solution.
As the problem states, this solution assumes that there is at least one space in the string.
public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}
public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;
for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space? If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;
for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}
}
This solution assumes that the string has at least one space.
{public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}
public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;
for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space? If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;
for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}
}}
public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}
public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;
for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space? If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;
for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}
}
This is my answer
public class Test
{
public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}
}
This is simple way to do it:
public class Test
{
public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}
}
The sol will give proper answer in a simple way.
public class Test
{
public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}
}
public class Durlav {
public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";
for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}
return lowers + spaces + uppers;
}
public static void main(String []args) {
String output = Durlav.sortString("x gBd ADbmY");
System.out.println(output);
}
}
public class AlphabetSorter {
public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";
for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}
return lowers + spaces + uppers;
}
public static void main(String []args) {
String output = AlphabetSorter.sortString("g cXSd FFGmY");
System.out.println(output);
}
}
public class AlphabetSorter {
public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";
for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}
return lowers + spaces + uppers;
}
public static void main(String []args) {
String output = AlphabetSorter.sortString("a cBd LkmY");
System.out.println(output); //result: acdkm BLY
}
}
public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
//char[] charArray = new char [] { 'c', 'A', 'B', 'd', ' '};
Sort(charArray);
System.out.print(charArray);
}
public static void Sort(char[]charArray) {
int writePos = charArray.length - 1;
// Search for capital letters in first pass
char lower = 'A';
char upper = 'Z';
for (int pass = 0; pass < 2; pass++)
{
for (int readPos = writePos; readPos >=0; readPos--) {
if (charArray[readPos] >= lower && charArray[readPos] <= upper) {
if (readPos == writePos) {
// This character is in the correct place already
writePos--;
continue;
}
// Put the character in its correct place
// and shift the remaining characters left to fill
// in the gap
char temp = charArray[readPos];
System.arraycopy(charArray, readPos+1, charArray, readPos, writePos - readPos);
charArray[writePos--] = temp;
}
}
lower=upper=' '; // Search for spaces in second pass
}
}
}
public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
//char[] charArray = new char [] { 'c', 'A', 'B', 'd', ' '};
Sort(charArray);
System.out.print(charArray);
}
public static void Sort(char[]charArray) {
int writePos = charArray.length - 1;
// Search for capital letters in first pass
char lower = 'A';
char upper = 'Z';
for (int pass = 0; pass < 2; pass++)
{
for (int readPos = writePos; readPos >=0; readPos--) {
if (charArray[readPos] >= lower && charArray[readPos] <= upper) {
if (readPos == writePos) {
// This character is in the correct place already
writePos--;
continue;
}
// Put the character in its correct place
// and shift the remaining characters left to fill
// in the gap
char temp = charArray[readPos];
System.arraycopy(charArray, readPos+1, charArray, readPos, writePos - readPos);
charArray[writePos--] = temp;
}
}
lower=upper=' '; // Search for spaces in second pass
}
}
}
The algorithm works from the back of the string forwards, first placing the capital letters in their correct position, while shifting the string left. After the capital letters are placed, the algorithm does the same thing, placing the spaces in their correct position. Once the capital letters and spaces are positioned, the lowercase letters will automatically be in their correct places. I think this should still be O(N).
The space complexity is not constant. The difference between writePos and readPos might be O(n), hence the arraycopy method needs O(n) space. Moreover, you used arraycopy only for once within each scan, which probably "covers" some elements. I think to ensure no char/element is lost, one should use swap or copying twice.
The array copy uses the same array as the source and destination, so there is no additional space used. The copy shifts all elements left into the gap left over. The only question for me is the running time of the copy. The worst case scenario is presented when there is an equal number of spaces, followed by an equal number of uppercase letters, followed by an equal number of lowercase letters.
Do you mean that within each `if (charArray[readPos] >= lower && charArray[readPos] <= upper)` branch, the sub-array is only shifted by one unit? If so, then, true, only constant time is used. However, in the worst case, \Theta(n) elements will be shifted for \Theta(n) times. Hence the time complexity might be O(n^2). Anyway, the code above does not seem to be a worst case O(n) algorithm.
package com.sumit.crthcoin.chapter2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SortAlphabets {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
List<Character> small = new ArrayList<Character>();
List<Character> large = new ArrayList<Character>();
for (int i=0;i<input.length();i++)
{
Character ch = input.charAt(i);
if(Character.isUpperCase(ch))
large.add(ch);
else if(Character.isLowerCase(ch))
small.add(ch);
}
Character[] upper = large.toArray(new Character[large.size()]);
Character[] lower = small.toArray(new Character[small.size()]);
StringBuilder sb1 = new StringBuilder(small.size());
for (Character ch : small)
sb1.append(ch);
String r1 = sb1.toString();
StringBuilder sb2 = new StringBuilder(large.size());
for(Character ch: large)
sb2.append(ch);
String r2 = sb2.toString();
char[] array1 = r1.toCharArray();
char[] array2 = r2.toCharArray();
Arrays.sort(array1);
Arrays.sort(array2);
String res = String.copyValueOf(array1) + " " + String.copyValueOf(array2);
System.out.println(res);
}
}
This is not a clean one; but it works.
bool inrange(char a, char b, int& dir)
{
// check if b is in the range of a
// if a is CAPS, check if b is CAPS
dir = 0;
if ('A' <= a && a <= 'Z')
{
if (('A' <= b && b <= 'Z') || b == ' ')
{
return true;
}
else
{
if (b == ' ')
{
dir = 0;
return false;
}
else
{
dir = 0;
return false;
}
}
}
else if ('a' <= a && a <= 'z')
{
if ('a' <= b && b <= 'z')
{
return true;
}
else
{
if (b == ' ')
{
dir = 1;
return false;
}
else
{
dir = 1;
return false;
}
}
}
else if (a == ' ')
{
if (b == ' ')
{
return true;
}
else
{
if ('A' <= b && b <= 'Z')
{
dir = -1;
return false;
}
else if ('a' <= b && b <= 'z')
{
dir = 0;
return false;
}
}
}
return false;
}
void strmemove(char* dest, char* src, int size)
{
while(size)
{
*dest = *src;
dest--;
src--;
size--;
}
}
bool isSmall(char c)
{
return ('a' <= c )&& (c <= 'z');
}
bool isBig(char c)
{
return ('A' <= c )&& (c <= 'Z');
}
bool isSpace(char c)
{
return (' ' == c);
}
void encode(char str[])
{
int front = 1, back = 0;
int moveDir = 0;
unsigned long size = strlen(str);
int backSmall = 0, backSpace = 0;
printf("new string = %s, len=%zu\n", str, strlen(str));
while(back < size)
{
if (inrange(str[front], str[back], moveDir))
{
front++;
}
else
{
if (moveDir == -1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSpace);
str[backSpace] = temp;
front++;
back++;
backSpace++;
}
else if (moveDir == 1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSmall);
str[backSmall] = temp;
back++;
front++;
backSmall++;
backSpace++;
}
else
{
if (isSmall(str[back]))
{
backSmall++;
backSpace++;
}
if (isSpace(str[back]))
{
backSpace++;
}
back = front;
front++;
}
}
}
printf("new string = %s, len=%zu\n", str, strlen(str));
}
void encode_test()
{
char str[] = "aEBcfD Ah eK ";
encode(str);
char str1[] = "EB D A K ";
encode(str1);
char str2[] = "E a B b D d A a K k b";
encode(str2);
}
This is not a clean one; but it works.
bool inrange(char a, char b, int& dir)
{
// check if b is in the range of a
// if a is CAPS, check if b is CAPS
dir = 0;
if ('A' <= a && a <= 'Z')
{
if (('A' <= b && b <= 'Z') || b == ' ')
{
return true;
}
else
{
if (b == ' ')
{
dir = 0;
return false;
}
else
{
dir = 0;
return false;
}
}
}
else if ('a' <= a && a <= 'z')
{
if ('a' <= b && b <= 'z')
{
return true;
}
else
{
if (b == ' ')
{
dir = 1;
return false;
}
else
{
dir = 1;
return false;
}
}
}
else if (a == ' ')
{
if (b == ' ')
{
return true;
}
else
{
if ('A' <= b && b <= 'Z')
{
dir = -1;
return false;
}
else if ('a' <= b && b <= 'z')
{
dir = 0;
return false;
}
}
}
return false;
}
void strmemove(char* dest, char* src, int size)
{
while(size)
{
*dest = *src;
dest--;
src--;
size--;
}
}
bool isSmall(char c)
{
return ('a' <= c )&& (c <= 'z');
}
bool isBig(char c)
{
return ('A' <= c )&& (c <= 'Z');
}
bool isSpace(char c)
{
return (' ' == c);
}
void encode(char str[])
{
int front = 1, back = 0;
int moveDir = 0;
unsigned long size = strlen(str);
int backSmall = 0, backSpace = 0;
printf("new string = %s, len=%zu\n", str, strlen(str));
while(back < size)
{
if (inrange(str[front], str[back], moveDir))
{
front++;
}
else
{
if (moveDir == -1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSpace);
str[backSpace] = temp;
front++;
back++;
backSpace++;
}
else if (moveDir == 1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSmall);
str[backSmall] = temp;
back++;
front++;
backSmall++;
backSpace++;
}
else
{
if (isSmall(str[back]))
{
backSmall++;
backSpace++;
}
if (isSpace(str[back]))
{
backSpace++;
}
back = front;
front++;
}
}
}
printf("new string = %s, len=%zu\n", str, strlen(str));
}
void encode_test()
{
char str[] = "aEBcfD Ah eK ";
encode(str);
char str1[] = "EB D A K ";
encode(str1);
char str2[] = "E a B b D d A a K k b";
encode(str2);
}
import java.util.*;
import java.io.*;
class B{
void fun(StringBuffer s){
int l=s.length(),m=0,n=0,o=0,k;
int low[]=new int[l];
int up[]=new int[l];
int sp[]=new int[l];
for(int i=0;i<l;i++){
k=s.charAt(i);
if(k>=97 && k<=122){
low[m]=i;
m++;
}
else if(k==32){
sp[n]=i;
n++;
}
else if(k>=65 && k<=90){
up[o]=i;
o++;
}
}
for(int i=0;i<m;i++){
System.out.print(s.charAt(low[i]));
}
for(int i=0;i<n;i++){
System.out.print(s.charAt(sp[i]));
}
for(int i=0;i<o;i++){
System.out.print(s.charAt(up[i]));
}
System.out.println();
}
}
class A{
public static void main(String args[])throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
StringBuffer s1=new StringBuffer(s);
System.out.println(s1);
B b1=new B();
b1.fun(s1);
}
}
#include <stdio.h>
#include <stdlib.h>
#define CAPSL (1<<0)
#define SMALL (1<<1)
#define UNDERSCORE (1<<2)
#define SWAP(a, b) \
{ \
char c; \
c = *a; \
*a = *b; \
*b = c; \
}
char *start;
typedef enum ltype_ {
SMC = 0,
USC,
CAP,
} ltype;
ltype
gettype (char c)
{
if ((c >= 'a') && (c <= 'z')) return SMC;
if ((c >= 'A') && (c <= 'Z')) return CAP;
if (c == '_') return USC;
printf("Undefined type \n");
exit(1);
return SMC;
}
int
get_next_exp_flag (char c)
{
switch (gettype(c)) {
case SMC:
return (UNDERSCORE | CAPSL| SMALL);
case USC:
return (UNDERSCORE | CAPSL);
case CAP:
return CAPSL;
default:
printf("Fatal error \n");
exit(1);
}
}
int
get_current_flag (char c)
{
switch (gettype(c)) {
case SMC:
return (SMALL);
case USC:
return (UNDERSCORE);
case CAP:
return CAPSL;
default:
printf("Fatal error \n");
exit(1);
}
return -1;
}
#define EOLL '\0'
void
process_str( char *ptr)
{
int nef, cf;
char *save;
nef = get_next_exp_flag(*ptr);
ptr++;
while (*ptr != EOLL) {
cf = get_current_flag(*ptr);
save = ptr;
//printf("1. %c \n", *ptr);
while ((cf & nef) == 0) {
printf("Swap betw %c %c <%s>\n", *ptr, *(ptr-1), start);
getchar();
SWAP(ptr, (ptr-1));
if (ptr - 2 < start) {
break;
}
ptr -=2;// (??)
printf(" Now compare %c %c <%s>\n", *ptr, *(ptr+1), start);
getchar();
nef = get_next_exp_flag(*ptr);
ptr++;
cf = get_current_flag(*ptr);
}
ptr = save;
nef = get_next_exp_flag(*ptr);
printf("2. %c \n", *ptr);
ptr++;
}
}
int
main (int argc, char *argv[])
{
if (argc <= 1) return;
start = argv[1];
process_str(argv[1]);
printf("Final \n %s\n",start);
}
import java.lang.reflect.Array;
import java.util.Arrays;
public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{
}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;
}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);
}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}
}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}
}
import java.lang.reflect.Array;
import java.util.Arrays;
public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{
}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;
}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);
}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}
}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}
}
import java.lang.reflect.Array;
import java.util.Arrays;
public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{
}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;
}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);
}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args){
String s = "a cBd LkmY";
Tough t = new Tough();
char[] arr = s.toCharArray();
t.sortArray(arr);
}
public void sortArray(char[] s){
int start = 0;
start = specialSort(s, start, s.length, 0);
start = specialSort(s, start + 1, s.length, 1);
specialSort(s, start+1, s.length, 2);
for(int i=0; i<s.length; i++){
System.out.print(s[i]);
}
}
public int specialSort(char[] s, int start, int length, int type){
int index = 0;
int lower = -1;
for(int i = start; i<length;i++){
char c = s[i];
boolean status = compare(type, c);
if(status && lower == -1){
index = i;
continue;
} else if(!status && lower == -1){
lower = i;
continue;
} else{
if(lower >= 0 && status){
if(Math.abs(i - lower) == 1){
char temp = s[i];
s[i] = s[lower];
s[lower] = temp;
index = lower;
lower = i;
} else{
char temp = s[i];
for(int k=i-1; k>=lower; k--){
s[k+1] = s[k];
}
s[lower] = temp;
index = lower;
lower = lower + 1;
}
}
}
}
return index;
}
public boolean compare(int type, char a){
boolean status = false;
switch(type){
case 0: if(Character.isLowerCase(a))
status = true;
break;
case 1: if(a == ' ')
status = true;
break;
case 2: if(Character.isUpperCase(a))
status = true;
break;
}
return status;
}
}
// C# CODE
string str = "aH JgUk OliTe ";
string lower = "", space = "", upper = "";
foreach (char s in str)
{
if (char.IsLower(s)) lower += s.ToString();
else if (char.IsUpper(s)) upper += s.ToString();
else space += s.ToString();
}
Console.Write(lower + space + upper);
Console.ReadLine();
1] This C code is being tested in gcc.
The exact output is achieved using O(N2) and not by O(N).
In the following code, order of lower and upper case characters within the string is also maintained.
I/P: [ZtY cVj PkMl S]
O/P: [tcjkl ZYVPMS]
I have used a [char tmpchar variable] in my code for swapping.
2] #include<stdio.h>
#include<string.h>
int main()
{ char str[14]="ZtY cVj PkMl S";
lowspaceUpper(str);
}
lowspaceUpper(char *str)
{ int i,j,k;
char tmpchar;
printf("\nbefore sort:string=%s length=%d",str,strlen(str));
// Sorting Algorithm is used to swap characters according to the required sequence.
for(i=0;i<strlen(str);i++)
{
for(j=i+1;j<strlen(str);j++)
{
// the foll. conditions are used, if no swapping is required
if((str[i]==32 && str[j]==32))
continue;
else if((str[i]>=65 && str[i]<=90) && (str[j]>=65 && str[j]<=90))
continue;
else if((str[i]>=97 && str[i]<=122) && (str[j]>=97 && str[j]<=122))
continue;
else if(str[i]==32 && (str[j]>=65 && str[j]<=90))
continue;
else if((str[i]>=97 && str[i]<=122) && str[i]==32)
continue;
else if((str[i]>=97 && str[i]<=122) && (str[i]>=65 && str[i]<=90))
continue;
else{
if(str[i] >=65 && str[i] <=90) // foll condition is used if need to swap a Upper case with lower case or space
{
k=j;
tmpchar=str[k];
for(;k!=i;k--)
{
str[k]=str[k-1];
}
str[i]=tmpchar;
}else{ // foll condition is used if v need to swap a space with Upper case or Lower case
if(str[i]<str[j])
{
swap(&str[i],&str[j]);
}
}
}
}
printf("\niteration %d:string=%s",i,str);
}
printf("\nafter sort:string=%s length=%d",str,strlen(str));
printf("\n");
}
swap(char *ptr1,char *ptr2)
{
*ptr1 = (*ptr1) + (*ptr2); // x now becomes 15
*ptr2 = (*ptr1) - (*ptr2); // y becomes 10
*ptr1 = (*ptr1) - (*ptr2); // x becomes 5
}
How about this one.. Please command if it is not efficient!!
#include<stdio.h>
#include<string.h>
void Swap(char *a, char *b)
{
char tmp = *a;
*a = *b;
*b = tmp;
}
char *Sort(char *str)
{
int i, j, l = strlen(str);
for(i=0; i< l ; i++)
for(j=i; j<l; j++)
if(str[i]>str[j])
Swap(str + i, str + j);
return str;
}
int main()
{
char str[]= "a cBd LkmY";
int i,l=0, u=0;
char Lower[8]= "", Upper[8]= "";
for(i=0; str[i]; i++)
if(islower(str[i]))
Lower[l++] = str[i];
else if(isupper(str[i]))
Upper[u++] = str[i];
printf("%s %s", Sort(Lower), Sort(Upper));
return 0;
}
package prac;
import java.util.ArrayList;
public class SortChar {
public static void Rearrange(ArrayList<Character> textArray)
{
LeftToRight(textArray);
RightToLeft(textArray);
}
private static void LeftToRight(ArrayList<Character> textArray)
{
int iPos;
for (iPos = 0; iPos < textArray.size(); iPos ++)
{
if (textArray.get(iPos).equals(' '))
{
int iLower;
// Swap this space with the first lower-case character after it.
for (iLower = iPos + 1; (iLower < textArray.size()); iLower ++){
if(Character.isLowerCase(textArray.get(iLower))){
char temp= textArray.get(iLower);
textArray.remove(iLower);
textArray.add(iPos, temp);
iPos++;
}
}
}
}
}
private static void RightToLeft(ArrayList<Character> textArray)
{
int iPos;
if (textArray.size() == 0) return;
for (iPos = (textArray.size() - 1); iPos >= 0; iPos --)
{
if (textArray.get(iPos).equals( ' '))
{
int iUpper;
// Swap this space with the first lower-case character after it.
for (iUpper = iPos -1; (iUpper >=0); iUpper --){
if(Character.isUpperCase(textArray.get(iUpper))){
char temp= textArray.get(iUpper);
textArray.remove(iUpper);
textArray.add(iPos, temp);
iPos--;
}
}
}
}
}
public static void main(String[] args)
{
String Text = "ab CDe fGHi JK lm";
ArrayList<Character> TextArray = new ArrayList<Character>();
for (int a=0; a<Text.length();a++){
TextArray.add(Text.charAt(a));
}
System.out.println(Text);
Rearrange(TextArray);
String t="";
for(int index=0; index< TextArray.size();index++){
t=t.concat(TextArray.get(index).toString());
}
System.out.println(t);
}
}
Solution using Golang
package main
import "fmt"
import "unicode"
func sort(S *[]byte) {
marker := 0
//sort lower case
for index,value := range *S {
if unicode.IsLower(rune(value)) {
(*S)[index], (*S)[marker] = (*S)[marker], (*S)[index]
marker++
}
}
for i:=marker;i<len(*S);i++ {
if string((*S)[i])==" " {
(*S)[i], (*S)[marker] = (*S)[marker], (*S)[i]
marker++
}
}
}
func main() {
fmt.Println("Hello playground")
S := []byte("vHbR Tb TzzzA")
sort(&S)
fmt.Println(string(S))
}
1. First traverse the array to find the position of space as space position would be number of small characters +1.
2.now just again traverse the array and start from begining and pos[space+1]if find small char put before space.else put after space.
3.With this thier is no extra space an also in O(n).I hope you understand it.
1. First traverse the array to find the position of space as space position would be number of small characters +1.
2.now just again traverse the array and start from begining and pos[space+1]if find small char put before space.else put after space.
3.With this thier is no extra space an also in O(n).I hope you understand it.
Its a variation of Dutch National Flag problem but with 3 way partitioning.
- um01 August 13, 2015O(n) time complexity and not extrat space.
lower letter are first partition , space second and upper case third partition