Largest number formed by replacing k digits

[SlurrerOfSpeech]

I'm wondering if you guys can help me figure out where I'm going wrong here. The prompt is

Given k and an n-digit number, help Sandy determine the largest possible number she can make by changing k digits.

Full prompt here: https://www.hackerrank.com/challenges/richie-rich

My solution is slightly brute force, however it is working on all the test cases with smaller input and isn't timing out on the test cases with larger input (the output is incorrect or there is an unspecified runtime error). I've thoroughly unit tested each individual helper function and so I'm not sure why it isn't working as a whole. I've added comments to help describe what's going on.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution
{
   
    private static readonly List<char> _Digits = new List<char>() { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

    // returns true or false depending on whether s is a palindrome   
    private static bool IsPalindrome(string s)
    {
        for(int i = 0, j = s.Length - 1; i < j; ++i, --j)
            if(s[i] != s[j])
                return false;
        return true;
    }
   
    // returns a copy of string s with the char-acter at index i replaced with c
    private static string ReplaceAt(string s, int i, char c)
    {
        if(s.Length < 1) // corner case
            return string.Empty;
        var sb = new StringBuilder(s);
        sb[i] = c;
        return sb.ToString();       
    }
   
   
    // returns all strings formed from replacing a digit of number with a different digit   
    public static IEnumerable<string> SingleDigitReplacements(string number)
    {
        for(int i = 0; i < number.Length; ++i)
            foreach(char c in _Digits.Where(d => number[i] != d))
                yield return ReplaceAt(number,i,c);
    }
   
    // returns all strings formed from replacing k digits of number with different digits
    public static IEnumerable<string> KDigitReplacements(string number, int k)
    {
        var nums = new HashSet<string>(); // use hash set because algorithm encounters repeats
        nums.Add(number); // k = 0, replaced no digits
       
        // k times, replace every digit of the number in nums with the 9 other digits, 
        // add that replacement to nums
        // e.g. "13", k = 1 ---> "13" (no digits replaced)
        //                       "03", "23", ..., "93" (1st digit replaced)
        //                       "10", "11", "12", "14", ..., "19" (2nd digit replaced)
        for(int i = 0; i < k; ++i)
        {
            // the reason I have to use an inner set is because the compiler doesn't
            // like me adding to the nums while I'm looping through it
            var inner = new HashSet<string>();
            foreach(var num in nums)
                foreach(string replacement in SingleDigitReplacements(num))
                    inner.Add(replacement);
            foreach(string replacement in inner)
                nums.Add(replacement);
        }
        return nums;
    }
   
    static void Main(String[] args)
    {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int k = Convert.ToInt32(tokens_n[1]); // max number of replacements
        string number = Console.ReadLine(); // string representation of number
       
        var replacements = KDigitReplacements(number, k); // all replacements of k digits
        var palindromes = replacements.Where(numstr => IsPalindrome(numstr)); // filter out non-palindromes
        // find max, print to console
        try
        {
         var max = palindromes.Max(numstr => Int64.Parse(numstr));
          Console.WriteLine(max);
        }
        catch(InvalidOperationException e) // no max exists
        {
            Console.WriteLine("-1");  
        }
    }
}

 

[Mark44]

It would have been helpful to mention that the changed number has to be a palindrome. Per the examples on the page you linked to, for some numbers and some values of k, it's not possible to form a palindrome (e.g., 0011, with k = 1). In that case a value of -1 should be returned.

 

[SlurrerOfSpeech]

It would have been helpful to mention that the changed number has to be a palindrome. Per the examples on the page you linked to, for some numbers and some values of k, it's not possible to form a palindrome (e.g., 0011, with k = 1). In that case a value of -1 should be returned.

Oops. Forgot to mention that crucial detail.

 

[SlurrerOfSpeech]

Alright, I made an O(n) solution which is making the performance benchmarks and is passing 30/32 test cases! There must be some corner case I'm missing.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution
{   
    // returns true or false depending on whether the string underlying
    // the StringBuilder sb is a palindrome
    static bool IsPalindrome(StringBuilder sb)
    {
        for(int i = 0, j = sb.Length - 1; i < j; ++i, --j)
            if(sb[i] != sb[j])
                return false;
        return true;
    }
   
    static string LargestPalindromeAfterKReplacements(string number, int k)
    {
        // Finds the largest palindromic number (digits are the same in reverse order)
        // that can be formed by at most k replacements of digits.
        // e.g. "001", k=2 --> "909"
        //      "001", k=1 --> "101"
        //      "001", k=0 --> "-1" (not possible)
       
        var sb = new StringBuilder(number);
      
        var replacementIndices = Enumerable.Range(0, sb.Length).ToArray();
        for(int i = 0, j = sb.Length - 1; i < j && k > 0; ++i, --j)
        {
            if(sb[i] < sb[j])
            {
                sb[i] = sb[j];
                replacementIndices[i] = 1;
                k -= 1;
            }
            else if(sb[i] > sb[j])
            {
                sb[j] = sb[i];
                replacementIndices[i] = 1;
                k -= 1;
            }
        } 
       
        if(!IsPalindrome(sb))
            return "-1";
       
        for(int i = 0, j = sb.Length - 1; i <= j && k > 0; ++i, --j)
        {
            if(sb[i] != '9')
            {
                if(replacementIndices[i] == 1) // if made a replacement at index i
                {
                    sb[i] = '9';
                    sb[j] = '9';
                    k -= 1;
                }
                else if(k > 1) // didn't make a replacement at index i, and k > 1
                {
                    sb[i] = '9';
                    sb[j] = '9';
                    k -= 2;                    
                }
                else if(i == j) // didn't make a replacement at index i, and our pointers met
                {
                    sb[i] = '9';
                }
            }
        }
        // In case we ran out of replacement indices, 
        return sb.ToString();
    }
   
    static void Main(String[] args)
    {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int k = Convert.ToInt32(tokens_n[1]); // max number of replacements
        string number = Console.ReadLine(); // string representation of number
        string converted = LargestPalindromeAfterKReplacements(number, k);
        Console.WriteLine(converted);
    }
}