# String Algorithm - Validating If String Conversion Requires More Than One Edits

## Problem Statement

Write a program to validate how many edits (add, remove, or replace character) are required to convert a given string into another given string. You need to consider that comparison is case sensitive and whitespace is significant.

Example 1

Input: s1 = "bat" s2 = "bad"

Output

Only one edit is required to convert one string to another.

Explanation

One edit (character 't' needs to be replaced by 'd') is required to convert s1 into s2.

Example 2

Input: s1 = "belt" s2 = "bel"

Output

Only one edit is required to convert one string to another

Explanation

One edit (character 't' needs to be removed or deleted) is required to convert s1 into s2.

Example 3

Input: s1 = "sea" s2 = "seat"

Output

Only one edit is required to convert one string to another

Explanation

one edit (character 't' needs to be added) is required to convert s1 into s2.

Example 4

Input: s1 = "salt" s2 = "sa"

Output

more than one edit

Explanation

more than one edit (character 'l' and 't' need to be removed) is required to convert s1 into s2.

Example 5

Input: s1 = "Salt" s2 = "sal"

Output

More than one edit

Explanation

More than one edit (character 't' needs to be removed and 'S' need to be replaced by 's') is required to convert s1 into s2.

Example 6

Input: s1 = "sea food" s2 = "seafoo"

Output

more than one edit

Explanation

more than one edit (character 'd' needs to be removed and ' ' need to be removed ) is required to convert s1 into s2.

Solution

Look at the steps described for an algorithm
• Compare the length of two strings and if the difference between these two strings is more than one character then print the result “more than one edit is required to convert one string to another” because to convert one string to another string more than one edits (add, remove, or replace character) are required.
• Find out a longer and smaller string based on the length difference, if the difference is less than 0 then the second given string is the longer string OR if the difference is more than 0 then first given string is the longer string OR difference equals to 0 then both strings are of the same length
• Convert both the given strings into an array of a type character
• Declare a variable to store the count of edits required
• Iterate through string character set while loop reaches the end of longer string length or end of smaller string length,

• check the value of variable edit counter, if more than one edit is found then return failure signal and print the result “more than one edit is required to convert one string to another”
• match the character of given strings (longer and smaller)

• if character matches then increment the counter for both smaller and longer string index otherwise,
• if the character does not match then do the following,

• increment the index counter for longer string and
• Increment the index counter for smaller string if and only if the length of smaller and longer is same
• increment the edit counter

• finally, print “only one edit is required to convert one string to another”
1. class Program {
2.  static void Main(string[] args) {
3.   Console.Write("Please enter first string to be processed: ");
5.   Console.WriteLine();
6.   Console.Write("Please enter second string to be processed: ");
8.
9.   if (CompareLength(firstInputString, secondInputString) == false// if length difference is more than 1 then more than one edit is required.
10.   {
11.    Console.WriteLine("more than one edit");
12.   } else {
13.    Console.WriteLine(FindEditCount(firstInputString, secondInputString) == false ?
14.     "more than one edit is required to convert one string to another" :
15.     "only one edit is required to convert one string to another");
16.   }
17.
19.  }
20.
21.  private static bool FindEditCount(string firstInputString, string secondInputString) {
22.   // find out longer and smaller string based on the length difference
23.   // difference is less than 0 then second given string is the longer string
24.   // OR difference is more than 0 then first given string is the longer string
25.   // OR difference equals to 0 then both string are of same length
26.   string longerString = firstInputString;
27.   string smallerString = secondInputString;
28.   int val = longerString.Length - smallerString.Length;
29.
30.   if (val < 0) {
31.    longerString = secondInputString;
32.    smallerString = firstInputString;
33.   }
34.
35.   int smallerStringIndex = 0;
36.   int longerStringIndex = 0;
37.   int editCount = 0;
38.
39.   char[] longerStringCharacterSet = longerString.ToCharArray();
40.   char[] smallerStringCharacterSet = smallerString.ToCharArray();
41.
42.   //continue iterate through string character set while loop reach at the end of longer string length or end of smaller string length
43.   while (longerStringCharacterSet.Length > longerStringIndex && smallerStringCharacterSet.Length > smallerStringIndex) {
44.    if (editCount > 1) return false// if more than one edit found then return failure signal
45.
46.    //match character of given strings (longer and smaller) if character match then increment the counter for both smaller and longer string index
47.    if (longerStringCharacterSet[longerStringIndex] == smallerStringCharacterSet[smallerStringIndex]) {
48.     longerStringIndex++;
49.     smallerStringIndex++;
50.    } else {
51.     // if do not match always increment the index counter for longer string
52.     longerStringIndex++;
53.     if (val == 0)
54.      // if do not match and length of smaller and longer is same
55.      // then increment the index counter for smaller string too
56.      smallerStringIndex++;
57.     editCount++;
58.    }
59.   }
60.
61.   return true;
62.  }
63.
64.  /// <summary>
65.  /// Compare the length of two given strings.
66.  /// </summary>
67.  /// <param name="firstInputString">First given string</param>
68.  /// <param name="secondInputString">Second given string</param>
69.  /// <returns></returns>
70.  private static bool CompareLength(string firstInputString, string secondInputString) {
71.   return Math.Abs(firstInputString.Length - secondInputString.Length) <= 1;
72.  }
73. }
Time Complexity

O(n )

array iteration takes O(n) time to iterate through n characters 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