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”

class Program {
static void Main(string[] args) {
Console.Write("Please enter first string to be processed: ");
var firstInputString = Console.ReadLine();
Console.WriteLine();
Console.Write("Please enter second string to be processed: ");
var secondInputString = Console.ReadLine();
if (CompareLength(firstInputString, secondInputString) == false) // if length difference is more than 1 then more than one edit is required.
{
Console.WriteLine("more than one edit");
} else {
Console.WriteLine(FindEditCount(firstInputString, secondInputString) == false ?
"more than one edit is required to convert one string to another" :
"only one edit is required to convert one string to another");
}
Console.ReadLine();
}
private static bool FindEditCount(string firstInputString, string secondInputString) {
// find out longer and smaller string based on the length difference
// difference is less than 0 then second given string is the longer string
// OR difference is more than 0 then first given string is the longer string
// OR difference equals to 0 then both string are of same length
string longerString = firstInputString;
string smallerString = secondInputString;
int val = longerString.Length - smallerString.Length;
if (val < 0) {
longerString = secondInputString;
smallerString = firstInputString;
}
int smallerStringIndex = 0;
int longerStringIndex = 0;
int editCount = 0;
char[] longerStringCharacterSet = longerString.ToCharArray();
char[] smallerStringCharacterSet = smallerString.ToCharArray();
//continue iterate through string character set while loop reach at the end of longer string length or end of smaller string length
while (longerStringCharacterSet.Length > longerStringIndex && smallerStringCharacterSet.Length > smallerStringIndex) {
if (editCount > 1) return false; // if more than one edit found then return failure signal
//match character of given strings (longer and smaller) if character match then increment the counter for both smaller and longer string index
if (longerStringCharacterSet[longerStringIndex] == smallerStringCharacterSet[smallerStringIndex]) {
longerStringIndex++;
smallerStringIndex++;
} else {
// if do not match always increment the index counter for longer string
longerStringIndex++;
if (val == 0)
// if do not match and length of smaller and longer is same
// then increment the index counter for smaller string too
smallerStringIndex++;
editCount++;
}
}
return true;
}
/// <summary>
/// Compare the length of two given strings.
/// </summary>
/// <param name="firstInputString">First given string</param>
/// <param name="secondInputString">Second given string</param>
/// <returns></returns>
private static bool CompareLength(string firstInputString, string secondInputString) {
return Math.Abs(firstInputString.Length - secondInputString.Length) <= 1;
}
}

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