String match based on upper-lower case letters in javascripty

Question

I have been asked this question in the technical interview for JavaScript today and I failed but I am still unable to find a solution. The question and the solution I came up with is in the following. I achieved to pass some of the test cases but code still does not work in every circumstances. if somebody helps me to solve it in an efficient way, I'd appreciate.

You are given a String, input, comprised of alphabetical letters with varying case.

These letters should create pairs with one another, based on case. For example, the letter 'N forms a "matching pair' with the letter 'a', in that order.

Rules:

The first letter must be upper-case.
Every upper-case letter must be followed by its lower-case version or any upper-case letter.
When an upper-case letter is followed by its lower-case version, those two letters are considered a "matching pair and can then be disregarded from further match consideration.
If any of these rules are broken or a lower-case letter is encountered that does not create a "matching pair' with its nearest un-matched left neighbour, that letter and all following letters are considered "un-matched".

Output: Your method should return the zero-based index of the last matching lower-case letter, or -1 if no pairs exist.

Limits: 0 < input length < 10,000 characters The optimal method has a running time of O(input length).

Sample input #1

ABba

Sample output #1

This is what i have done but it does not work for every test cases;

function stringMatch(str){ let word=str.split("") let lastIndex; if (word[0]===word[0].toUpperCase()){ for(let i=0;i<word.length;i++){ if(word[i]===word[i].toUpperCase()){ if(word[i].toLowerCase()===word[i+1] || word[i+1]===word[i+1].toUpperCase() ){ lastIndex=i } else{ return -1 } } else{ lastIndex=i } } return lastIndex } }

" in the technical interview" ... because this sort of problem is sure to come up in your day-to-day job... ;-) — Scott Sauyet
– Scott Sauyet, Commented Jul 3, 2018 at 19:53
@ScottSauyet The problem itself isn't important, it's the process of solving it that demonstrates competence in creating algorithms. — Barmar
– Barmar, Commented Jul 3, 2018 at 20:59
@Barmar Totally agree with you. They check your algorithm and data structure knowledge while solving problems. — Ugur Yilmaz
– Ugur Yilmaz, Commented Jul 3, 2018 at 22:56
@Barmar: I only half-agree. A good programmer should be able to demonstrate knowledge of interesting algorithms and useful data structures. But doing so in a toy problem does not show that she has actually grasped what's necessary to solve real-world problems. And in my experience, those who can solve such things on the whiteboard end up not being any better on a team than those who cannot. — Scott Sauyet
– Scott Sauyet, Commented Jul 4, 2018 at 1:20

Mark · Accepted Answer · 2018-07-03 22:27:31Z

A nice way to do this is with a stack that holds your uppercase letters. The next element of the stack should always be the next lower case you are trying to match.

Loop through the string and for each letter, if it's uppercase, push it on the stack and continue. If it's lower case, pop one off the stack and compare. If they match set the index as the last matched and continue, if they don't your done, return the last matched index.

const isUpper = (l) => l === l.toUpperCase() function findUnmatchedIndex(str) { let stack = [] let lastMatch = -1 for (let i = 0; i < str.length; i++) { let letter = str[i] if (isUpper(letter)) { stack.push(letter); continue; } let next = stack.pop() if (next !== letter.toUpperCase()) return lastMatch lastMatch = i } return lastMatch } console.log(findUnmatchedIndex('ABba')) console.log(findUnmatchedIndex('ABCcDEedFeGHi')) console.log(findUnmatchedIndex('ABCbDEedFeGHi'))

Thanks! Is this the optimum solution? What is the complexity of this algorithm? I think it is linear time, right? And if it's not, is there anyway to enhance the efficiency? @Mark_M
@UgurYilmaz I'm not sure if it's optimal, but It should be O(n) in the worst case if we assume that javascript's array.push() and array.pop() are both constant time operations. I don't see how we could do better than O(n), but it's easy to be wrong about that.
I understand. I have to add that it is a very good solution. It was the easiest one to understand compared to the other solutions. I hope this solution would be helpful for my next interviews! @Mark_M
@UgurYilmaz glad I could help. Good luck with the interviews!

Scott Sauyet · Accepted Answer · 2018-07-03 20:22:13Z

Without more test cases, I'm not certain about this. But this looks like it might meet the requirements.

const isLower = (c) => 'a' <= c && c <= 'z' const final = (stack) => stack[stack.length - 1] const initial = (stack) => stack.slice(0, stack.length - 1) const check = (str) => str.split('').reduce( ({lastIndex, failed, stack}, c, idx) => failed ? {lastIndex, failed, stack} // one reason not to do this with reduce. : isLower(c) ? c === final(stack) ? {lastIndex: idx, failed, stack: initial(stack)} : {lastIndex, failed: true, stack} : {lastIndex, failed, stack: stack.concat(c.toLowerCase())}, {lastIndex: -1, failed: false, stack: []} ).lastIndex console.log(check('ABba'))

Collectives™ on Stack Overflow

String match based on upper-lower case letters in javascripty

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related