String Algorithm - URLify

Problem Statement

 

Write a program to replace all spaces in a string with '%20'. You may assume that the string has enough space at the end to hold the additional characters and that you are given the "true" length of the string.

 

Example 1 

 

Input: s1 = "Hemant Jindal"

Output: Hemant%20Jindal

 

Example 2

 

Input: s1 = "Tic Toe"

Output: Tic%20Toe

 

Solution 

 

Look at the steps described for an algorithm

• Find out the length of the given string
• Convert the given string into an array of type character
• Find out the count of spaces within the input string
• Multiply the number of spaces with 2 to find out the extra space required to replace ' ' with '%20'  for example if there is one ' ' space then we need two extra places the given string to add '%20'
• Add extra spaces required to shift characters and replace ' ' with '%20'
• Iterate through the given string but note that starts from the end and working backward because we have added an extra buffer at the end, which allows us to change characters without worrying about what we're overwriting.
  
  
• If ' ' space found then replace ' ' with '%20'
• If not found then shift the current character by 2 places and continue iteration
  
  
• Finally, print the modified string.

class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Please enter string to be processed: ");
            var inputString = Console.ReadLine();
            URLifyString(inputString);
            Console.ReadLine();
        }

        private static void URLifyString(string inputString)
        {
            if (inputString != null)
            {
                //Find out the length of the given string
                int inputStringLength = inputString.Length;
                //Convert the given string into an array of type character
                char[] inputCharacterSet = inputString.ToCharArray();

                //Find out the count of spaces within the input string
                int spaceInStringCount = 0;
                for (int indexCount = 0; indexCount < inputStringLength; indexCount++)
                {
                    if (inputCharacterSet[indexCount] == ' ')
                    {
                        spaceInStringCount++;
                    }
                }

                // multiply the number of spaces with 2 to find out the extra space required to replace ' ' with '%20'
                // for example if there is one ' ' space then we need two extra places
                // the given string to add '%20'
                int extraSpacesRequired = (spaceInStringCount * 2);
                //add extra spaces required to shift characters and replace ' ' with '%20'
                inputCharacterSet = inputCharacterSet.Concat(new char[extraSpacesRequired]).ToArray();
                int inputCharacterSetCurrentIndex = inputStringLength - 1 + extraSpacesRequired;

                //iterate through the given string but note that start from the end and working backwards because
                //we have added an extra buffer at the end, which allows us to change characters without worrying about what we're overwriting.
                for (int inputIndex = inputStringLength - 1; inputIndex >= 0; inputIndex--)
                {
                    //if ' ' space found then replace ' ' with '%20'
                    if (inputCharacterSet[inputIndex] == ' ')
                    {
                        inputCharacterSet[inputCharacterSetCurrentIndex--] = '0';
                        inputCharacterSet[inputCharacterSetCurrentIndex--] = '2';
                        inputCharacterSet[inputCharacterSetCurrentIndex--] = '%';
                    }
                    else
                    {
                        //if not found then shift current character by 2 places
                        inputCharacterSet[inputCharacterSetCurrentIndex--] = inputCharacterSet[inputIndex];
                    }
                }
                Console.Write("Modified string is :");
                Console.WriteLine(inputCharacterSet);
            }
        }
    }

Time Complexity

 

O(n) + O(n) = O(n)

 

Array iteration takes O(n) time to iterate through n characters to find out the number of ‘ ’ (space) where n is the length of the string.

 

Second array iteration  takes O(n) to replace ‘ ’ (space) with ‘%20’ where n is the length of the string

 

Note
Please feel free to propose or suggest a solution you might think can be followed to make it better and more optimized.