Untitled

 avatar
unknown
plain_text
20 days ago
2.5 kB
3
Indexable
'use strict';

const fs = require('fs');

// Helper function to check if a string can be rearranged into a palindrome
function canFormPalindrome(s) {
    const freq = new Map();
    
    // Count the frequency of each character
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (char !== '?') {
            freq.set(char, (freq.get(char) || 0) + 1);
        }
    }

    let oddCount = 0;

    // Check how many characters have odd frequencies
    for (let count of freq.values()) {
        if (count % 2 !== 0) {
            oddCount++;
        }
        // If there are more than one character with an odd frequency, it can't be a palindrome
        if (oddCount > 1) return false;
    }
    
    return true;
}

// Function to get the smallest lexicographically palindrome by replacing '?' characters
function getSmallestPalindrome(s) {
    // If it's impossible to form a palindrome
    if (!canFormPalindrome(s)) {
        return "-1";
    }

    // Convert the string into an array for easier manipulation
    let arr = s.split('');
    let left = 0, right = arr.length - 1;
    
    // Replace '?' by iterating from both ends
    while (left < right) {
        if (arr[left] === '?' && arr[right] === '?') {
            // If both are '?', replace them with 'a' (lexicographically smallest)
            arr[left] = arr[right] = 'a';
        } else if (arr[left] === '?') {
            // If the left is '?', replace it with the character on the right
            arr[left] = arr[right];
        } else if (arr[right] === '?') {
            // If the right is '?', replace it with the character on the left
            arr[right] = arr[left];
        }
        left++;
        right--;
    }

    // If the length is odd, the middle character may still be '?'
    if (arr.length % 2 !== 0 && arr[Math.floor(arr.length / 2)] === '?') {
        arr[Math.floor(arr.length / 2)] = 'a'; // Replace with 'a' (lexicographically smallest)
    }

    // Return the resulting palindrome as a string
    return arr.join('');
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    // Read the string input
    const s = readLine().trim();  // Assuming readLine() is available in your environment

    // Call the getSmallestPalindrome function
    const result = getSmallestPalindrome(s);

    // Log the result (for debugging)
    console.log(result);

    // Write the result to the output
    ws.write(result + '\n');
    ws.end();
}
Editor is loading...
Leave a Comment