# 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.
1. class Program
2.     {
3.         static void Main(string[] args)
4.         {
5.             Console.Write("Please enter string to be processed: ");
7.             URLifyString(inputString);
9.         }
10.
11.         private static void URLifyString(string inputString)
12.         {
13.             if (inputString != null)
14.             {
15.                 //Find out the length of the given string
16.                 int inputStringLength = inputString.Length;
17.                 //Convert the given string into an array of type character
18.                 char[] inputCharacterSet = inputString.ToCharArray();
19.
20.                 //Find out the count of spaces within the input string
21.                 int spaceInStringCount = 0;
22.                 for (int indexCount = 0; indexCount < inputStringLength; indexCount++)
23.                 {
24.                     if (inputCharacterSet[indexCount] == ' ')
25.                     {
26.                         spaceInStringCount++;
27.                     }
28.                 }
29.
30.                 // multiply the number of spaces with 2 to find out the extra space required to replace ' ' with '%20'
31.                 // for example if there is one ' ' space then we need two extra places
32.                 // the given string to add '%20'
33.                 int extraSpacesRequired = (spaceInStringCount * 2);
34.                 //add extra spaces required to shift characters and replace ' ' with '%20'
35.                 inputCharacterSet = inputCharacterSet.Concat(new char[extraSpacesRequired]).ToArray();
36.                 int inputCharacterSetCurrentIndex = inputStringLength - 1 + extraSpacesRequired;
37.
38.                 //iterate through the given string but note that start from the end and working backwards because
39.                 //we have added an extra buffer at the end, which allows us to change characters without worrying about what we're overwriting.
40.                 for (int inputIndex = inputStringLength - 1; inputIndex >= 0; inputIndex--)
41.                 {
42.                     //if ' ' space found then replace ' ' with '%20'
43.                     if (inputCharacterSet[inputIndex] == ' ')
44.                     {
45.                         inputCharacterSet[inputCharacterSetCurrentIndex--] = '0';
46.                         inputCharacterSet[inputCharacterSetCurrentIndex--] = '2';
47.                         inputCharacterSet[inputCharacterSetCurrentIndex--] = '%';
48.                     }
49.                     else
50.                     {
51.                         //if not found then shift current character by 2 places
52.                         inputCharacterSet[inputCharacterSetCurrentIndex--] = inputCharacterSet[inputIndex];
53.                     }
54.                 }
55.                 Console.Write("Modified string is :");
56.                 Console.WriteLine(inputCharacterSet);
57.             }
58.         }
59.     }

## 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.