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

|

528 Discussions

|

  • naive_sage
     + 0 comments

    Hi @nabila_ahmed

    You are the author of Highest Value Palindrome problem. I was going through your solution and in your condition below condition else if((mark[l]==1 || mark[r]==1) && k>=1) { k-=1; ans[l] = ans[r] = '9'; } You are decrementing k by 1 but it should be decremented by 2 because we are changing both ans[l] and ans[r] in theelse part which requires 2 moves. If only 1 move is left how is this condition justified!!!

  • naive_sage
     + 0 comments

    @Xromeo

    I saw your solution in JAVA but I have a thing to ask..in the below condition else if (k - changes >= 1 && s.charAt(left) != s.charAt(right)) {

                        chars[left] = '9';
                    chars[right] = '9';
                    changes++;
                }

    In this condition, you are changing two characters but incrementing changes by 1. Why? For the string "092282" with k = 3, I debugged the code and in first loop the array was [2, 9, 2, 2, 9, 2] but in the above condition you are actually changing the values of both left and right index but incrementing the change by 1. I think it should be 2 . Am I mising something in the logic?

  • vuhuutuan0
     + 0 comments

    My answer with Typescript, simple

    function highestValuePalindrome(s: string, n: number, k: number): string {
    const replace = (s: string, i: number, c: string): string => {
        return s.substring(0, i) + c + s.substring(i + 1)
    }

    // 1. make [s] palidrome (required [k*] number of times), mark [i] that need to changes
    //  - using larger value to replace, saving [k] in 2. step
    let circles = []
    for (let i = 0; i < Math.floor(n / 2); i++) {
        let j = n - i - 1

        if (s[i] == s[j]) continue

        if (s[i] > s[j]) s = replace(s, j, s[i])
        if (s[i] < s[j]) s = replace(s, i, s[j])

        k--
        circles.push(i)

        // no more [k] left, it can't be palidrome
        if (k < 0) return '-1'
    }

    // 2. with remaining [k], replacement to increasing number value
    //  - with [i] that marked only need changes 1 orelse 2
    //  - with [s] is odd, changes the middle number if still have [k]
    for (let i = 0; i < Math.floor(n / 2); i++) {
        let j = n - i - 1

        if (s[i] != '9') {
            let k_ = circles.includes(i) ? 1 : 2
            if (k >= k_) {
                s = replace(s, i, '9')
                s = replace(s, j, '9')
                k -= k_
            }
        }

    }
    if (n % 2 == 1 && k > 0) s = replace(s, Math.floor(n / 2), '9')
    
    // 3. return the final palidrome [s]
    return s
}

  • illogicalsleepi1
     + 0 comments
    def highestValuePalindrome(s, n, k):
    s = list(s)  
    left = 0
    right = n - 1
    mismatches = set()
    while left < right:
        if s[left] != s[right]:
            s[left] = s[right] = max(s[left], s[right])
            mismatches.add(left)
            k -= 1
        if k < 0: 
            return '-1'
        left += 1
        right -= 1
        
    left = 0
    right = n - 1
    while left <= right:
        if left == right: 
            if k > 0:
                s[left] = '9'
        elif s[left] != '9':  
            if left in mismatches: 
                if k >= 1:
                    s[left] = s[right] = '9'
                    k -= 1
            elif k >= 2:  
                s[left] = s[right] = '9'
                k -= 2
        left += 1
        right -= 1

    return ''.join(s)

  • alex_k5
     + 0 comments
        if n == 1 and k > 0:
        return '9'
    count = sum([1 for i in range(n//2) if s[i] != s[-i-1]])
    if k < count:
        return '-1'
    ex = k-count
    s = list(s)
    for i in range(n//2):
        if s[i] == s[-i-1] != '9' and ex > 1:
            s[i] = s[-i-1] = '9'
            ex -=2
        elif s[i] != s[-i-1]:
            if s[i] == '9' or s[-i-1] == '9':
                s[i] = s[-i-1] = '9'
            else:
                if ex > 0:
                    s[i] = s[-i - 1] = '9'
                    ex -= 1
                else:
                    s[i] = s[-i - 1] = max(s[i], s[-i - 1])
    if ex > 0 and n % 2 == 1:
        s[n//2] = '9'
    return ''.join(s)