We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Highest Value Palindrome
  5. Discussions

Highest Value Palindrome

Sort by

recency

|

533 Discussions

|

  • enix12enix
     + 0 comments
    fn highestValuePalindrome(s: &str, n: i32, k: i32) -> String {
    let mut chs: Vec<char> = s.chars().collect();
    let mut k = k;
    let mut left: usize = 0;
    let mut right: usize = n as usize - 1;
    let mut cnt = 0;
    
    while left < right {
        if chs[left] != chs[right] {
            cnt += 1;
        }
        left += 1;
        right -= 1;
    }
    
    if k < cnt {
        return "-1".to_string();
    }
    
    left = 0;
    right = n as usize - 1;
    let mut changed: Vec<bool> = vec![false;chs.len()/2];
    while left < right {
        if chs[left] > chs[right] {
            chs[right] = chs[left];
            changed[left] = true;
            k -= 1;
        } else if chs[left] < chs[right] {
            chs[left] = chs[right];
            changed[left] = true;
            k -= 1;
        }
        left += 1;
        right -= 1;
    }
    
    left = 0;
    right = n as usize - 1;
    while left < right {
        if k > 0 && changed[left] && chs[left] != '9' {
            k -= 1;
            chs[left] = '9';
            chs[right] = '9';
        } else if k > 1 && !changed[left] && chs[left] != '9' {
            k -= 2;
            chs[left] = '9';
            chs[right] = '9'
        }
        left += 1;
        right -= 1;
    }
    
    if n % 2 == 1 && k > 0 {
        chs[left] = '9';
    }
    
    chs.into_iter().collect()
}

  • quote_unquote
     + 0 comments
    /*
 * Complete the 'highestValuePalindrome' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts following parameters:
 *  1. STRING s
 *  2. INTEGER n
 *  3. INTEGER k
 */

void _print(const set<size_t>& v) {
    for_each(
        v.begin(),
        v.end(),
        [](int t) { cout << t << " "; }
    );
    cout << endl;
}

set<size_t> _f(const string& s) {
    set<size_t> rx;
    size_t n = s.size();
    size_t k = static_cast<size_t>(floor(n / 2));
    size_t j;
    for (size_t i = 0; i < k; ++i) {
        j = n - 1 - i;
        if (s[i] != s[j]) {
            rx.insert(i);
        }
    }
    return rx;
}

char lx(char c1, char c2) {
    return (c1 > c2) ? c1 : c2;
}

string highestValuePalindrome(string s, int n, int k) {
    
    if (k >= n) {
        return string(n, '9');
    }

    size_t i, j;
    
    auto ix = _f(s);
    // _print(ix);
    if (ix.size() > k) { return "-1"; }
    
    for (auto ii: ix) {
        j = n - 1 - ii;
        auto c = lx(s[ii], s[j]);
        s[ii] = c;
        s[j] = c;
        k--;        
    }

    i = 0;
    j = n - 1 - i;
    while ((i < j) && (k > 0)) {
        if (s[i] != '9') {
            if ((ix.find(i) != ix.end()) && (k >= 1)) {
                s[i] = '9';
                s[j] = '9';
                k--;
            } else if (k >= 2) {
                s[i] = '9';
                s[j] = '9';
                k -= 2;
            }
        }
        i++;
        j--;
    }

    if ((k > 0) && (n % 2 == 1)) {
        j = static_cast<size_t>((n - 1) / 2);
        s[j] = '9';
        k--;
    }
    
    return s;
}

  • vituan121002
     + 0 comments

    Here is my c# solution: 

        public static string highestValuePalindrome(string s, int n, int k)
    {
        int left = 0, right = s.Length - 1;
        int remain = k;
        List<char> newS = new List<char>(s);
        List<bool> changedMark = Enumerable.Repeat(false, n).ToList();
        while (left < right){
            if (remain <= 0 && newS[left] != newS[right]) return "-1"; 
            if (newS[left] != newS[right]){
                remain--;
                if (newS[left] > newS[right]) newS[right] = newS[left];
                if (newS[right] > newS[left]) newS[left] = newS[right];
                   changedMark[left] = true; 
            }
            left++;
            right--;
        }
        left = 0; right = s.Length - 1;
        while (remain > 0 && left < right){    
            if (newS[left] != '9'){             
                if (changedMark[left])
                { 
                    newS[left] = newS[right] = '9';
                    changedMark[left] = false; 
                    remain --;
                }
                else if (remain >= 2){
                    newS[left] = newS[right] = '9';
                    changedMark[left] = false; 
                    remain -=2;
                }
            }
            left++;
            right--;      
        }     
        if (remain >= 1 && n % 2 == 1) newS[n/2] = '9';
        string result = new string(newS.ToArray());
        return result;
    }
}

  • Dmitry_Strakhov
     + 0 comments

    Here is my C# solution:

    public static string HighestValuePalindrome(string s, int k) {
        char[] chars = s.ToCharArray();
        
        // calculate count of unbalanced pairs in the string
        int m = 0;
        int i1 = 0;
        int j1 = s.Length - 1;

        while(i1 < j1) {
            if(s[i1] != s[j1])
                m++;
            i1++;
            j1--;
        }

        // it is not enough 'k' in advance
        if(k < m)
            return "-1";

        int i2 = 0;
        int j2 = s.Length - 1;

        // we prefer both '9' if possible
        while(i2 < j2) {
            if(CanSetBoth9Digits()) {
                chars[i2] = chars[j2] = '9';
                k -= 2;
                if(s[i2] != s[j2])
                    m -= 1;
            }
            else if(s[i2] > s[j2]) {
                chars[j2] = chars[i2];
                k--;
                m--;
            }
            else if(s[i2] < s[j2]) {
                chars[i2] = chars[j2];
                k--;
                m--;
            }

            i2++;
            j2--;
        }
        
        if(i2 == j2 && k > 0)
            chars[i2] = '9';
        
        return new string(chars);


        bool CanSetBoth9Digits() {
            if(s[i2] == '9' || s[j2] == '9')
                return false;
            bool digitsEqual = s[i2] == s[j2];
            return (!digitsEqual && k > m) || (digitsEqual && k > m + 1);
        }
    }

  • icywind
     + 0 comments

    **C# Solution O(n) time 0(1) space **

    public static string highestValuePalindrome(string s, int n, int k)
{
    /* Thought process
    if s is palindrome, then easily update
    if s is not palindrome, then need to know how many different pair D.
    If k < D, then nope. Otherwise,
    If k == D, change all half of the diff pairs
    if k > D, after above, change from the furthest out pair to inside
    */
    char[] arr = s.ToArray<char>();
    HashSet<int> updated = new HashSet<int>();
    int l = 0, r = n-1;
    int mid = n/2;
    int replace = k;
    while ( l < r) {
        if (s[l] == s[r]) { 
            l++; r--;
            continue;
        } 
        if (replace>0) {
            if (s[l] > s[r]) {
                arr[r] = arr[l];
            } else {
                arr[l] = arr[r];
            }
            updated.Add(l);
            replace--;
        } else {
            if (l < mid) {
                return "-1";
            }
        }
        l++; r--;
    } 
    l = 0;
    r = n-1;
    while(replace > 0 && l<=r) {
        if (arr[l]<'9') {
            if (l == r) {
                arr[l] = '9';
                break;
            }
            if (updated.Contains(l)) {
                // need one change only, since one is counted to update to non-9
                arr[l] = '9';
                arr[r] = '9';
                replace--;
            } else if (replace > 1) {
                arr[l] = '9';
                arr[r] = '9';
                replace-=2;
            }
        }
        l++; r--;
    }

    return new string(arr);