2
\$\begingroup\$

A coding challenge in which we are to write a function that compares two strings and returns the one that is smaller. The comparison is both lexicographical and numerical, depending on the content of the strings as explained below and in the comments of the code.

Both strings may contain any characters. Consecutive numbers in the string are considered a single number. If during the search the character of only one string is a number, then that string is returned as numbers are lexicographically smaller than letters.

If during the search the characters of both strings are numbers, then parseInt(strX.slice(i)) checks if there are more consecutive digits in each string and returns the string whose number is numerically smaller.

Examples:

input: "a", "b" expected output: "a" since "a" comes before "b" alphabetically

input: "a1", "a2" expected output: "a1" since 1 comes before 2

input: "a10", "a2" expected output: "a2" since 2 comes before 10

Here is the code:

const smallestString = (str1, str2) => {
    // we only need to iterate through the shortest string
    const len = str1.length < str2.length ? str1.length : str2.length;
    for (let i = 0; i < len; i++) {
        // check if both letters are strings
        if (str1[i].toUpperCase() !== str1[i].toLowerCase() && str2[i].toUpperCase() !== str2[i].toLowerCase()) {
            if (str1[i] === str2[i]) { // if both letters are the same, continue
                continue;
            } else {
                return str1[i] < str2[i] ? str1 : str2; // otherwise return the string with the 'smaller' char at that index
            }
        } else if (!isNaN(str1[i] || !isNaN(str2[i]))) { // check if either char is a number
            if (!isNaN(str1[i]) && !isNaN(str2[i])) { // if both chars are numbers, return str with numerically smaller number
              return parseInt(str1.slice(i)) < parseInt(str2.slice(i)) ? str1 : str2;
            }
        } else {
            return str1[i] < str2[i] ? str1 : str1;
        }
    }
    return str1; // if we get here then both strings are equal and either can be returned
}

console.log(smallestString('a10', 'a2')); // returns 'a2'

I am seeking any and all feedback about cleaning up the code and possibly improving the algorithm's current time complexity of O(n).

\$\endgroup\$
  • 1
    \$\begingroup\$ Can we assume ANSI encoding of the strings, or can they include extended Unicode characters? \$\endgroup\$ – dfhwze Jun 14 at 21:52
  • \$\begingroup\$ At this point I would only assume ANSI. \$\endgroup\$ – MadHatter Jun 14 at 21:53
  • 2
    \$\begingroup\$ Since you may have to compare every character, you can't get below $O(n)\$. \$\endgroup\$ – vnp Jun 14 at 21:53
  • \$\begingroup\$ I was pretty sure that the time complexity of this problem cannot be less than O(n), however, I would still like feedback for refactoring. \$\endgroup\$ – MadHatter Jun 14 at 21:55
  • 1
    \$\begingroup\$ What is the expected output of ('a10', 'ab')? \$\endgroup\$ – vnp Jun 14 at 22:19
2
\$\begingroup\$
        if (!isNaN(str1[i]) && !isNaN(str2[i])) { // if both chars are numbers, return str with numerically smaller number
          return parseInt(str1.slice(i)) < parseInt(str2.slice(i)) ? str1 : str2;
        }

seems like a bug. In case the numbers compare equal the code blindly returns the first string. Consider (a10c, a10b).


return str1; // if we get here then both strings are equal and either can be returned

seems like another bug. At this point we only know that the strings are equal up to the length of the shortest one, and the shortest one should be returned. Which one is shortest is not tested here.


The overall logic looks overcomplicated. Consider testing for numbers first; that would eliminate the need for a confusing toUpper/toLower mess, and the special case of special characters.

\$\endgroup\$
  • \$\begingroup\$ Well I didn't see the bug, but I fixed it now. Your feedback is greatly appreciated. \$\endgroup\$ – MadHatter Jun 14 at 23:37
  • \$\begingroup\$ Should I edit the post since this is Code Review? \$\endgroup\$ – MadHatter Jun 14 at 23:42
  • \$\begingroup\$ @SeanValdivia No. Post a follow-up question. \$\endgroup\$ – vnp Jun 14 at 23:51
  • \$\begingroup\$ Can you elaborate? Will the content of this follow-up question have the same code as above, but fixed? \$\endgroup\$ – MadHatter Jun 15 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.