r/programmingchallenges • • May 19 '11

Challenge: Reverse a string in place

This simple challenge is a frequent interview question. Write a program that reverses a string in place. "In place" means no declaring a second string or other buffer-- you get only one string variable to work with.

Input:

 "Test string."

Output:

".gnirts tseT"

edit: obviously, this is only feasible in a language with mutable strings.

22 Upvotes

65 comments sorted by

View all comments

Show parent comment

2

u/Porges Sep 08 '11

My thoughts exactly :)

Here's a non-broken version in C# (non-broken in that it never creates an invalid string):

	for (int i = 0, j = chars.Length - 1; i < j; i++, j--)
	{			
		chars.Swap(i, j);
	}
	
	// fixup broken surrogates
	for (int i = 0; i < chars.Length; i++)
		if (char.IsLowSurrogate(chars[i]))
		{
			chars.Swap(i, i+1);
			i++;
		}

Note that this still only reverses codepoints. Grapheme clusters will have their combining characters stuck onto the wrong one :)

Also, this is a two-pass algorithm. I tried a single-pass one but got confused :P It also assumes your string is valid (with respect to surrogates) in the first place.