Monday, February 8, 2021

Shortest distance to a character in a string

Problem: Given a string and a character in the given string, return an array of integers say result where result[i] will have the shortest distance of i to the given character's index in the input string.

Example:

Input: s = "nishant", c = "n"
Output: [0,1,2,2,1,0,1]


Approach: Approach can be understood easily by just looking at the implementation as it is fairly a very straight forward problem.


Implementation in C#:

        public static int[] ShortestToChar(string s, char c)

        {

            List<int> charPositions = new List<int>();

            for (int i = 0; i < s.Length; ++i)

            {

                if (s[i] == c)

                {

                    charPositions.Add(i);

                }

            }

            int[] result = new int[s.Length];

            int currCharIndex = 0;

            int nextCharIndex = currCharIndex + 1 == charPositions.Count ? -1 : currCharIndex + 1;

            for (int i = 0; i < s.Length; ++i)

            {

                if (i <= charPositions[currCharIndex] || nextCharIndex == -1)

                {

                    result[i] = Math.Abs(charPositions[currCharIndex] - i);

                }

                else

                {

                    if (Math.Abs(charPositions[currCharIndex] - i) >= charPositions[nextCharIndex] - i)

                    {

                        result[i] = charPositions[nextCharIndex] - i;

                        currCharIndex = nextCharIndex;

                        nextCharIndex = currCharIndex + 1 == charPositions.Count ? -1 : currCharIndex + 1;

                    }

                    else

                    {

                        result[i] = Math.Abs(charPositions[currCharIndex] - i);

                    }

                }

            }

            return result;

        }


Complexity: O(n)

No comments:

Post a Comment