Make Permalinks have a custom format?

Please see below. This will solve your problem for all future posts that you publish. I have tried this code. But to be on safer side, please backup your DB before you try or tray on staging.

function custom_unique_post_slug( $slug, $post_ID, $post_status, $post_type ) {

    $post = get_post($post_ID); 

    /* Set a flag to know if the post slug is already updated to required format */

    $is_slug_updated = get_post_meta( $post->ID, 'is_slug_updated' ); 

    /* define our two constant strings. You may change this to actual constants. */ 
    $first_const_str = "ConstantCustomString-";
    $second_const_str = "-ConstantCustomString";


    /* Check our flag and check post type is post and check if post is being published */
    if ( $post->post_type == 'post' && $post->post_status == 'draft' ) {        

        $slug = ucwords( str_replace("-", " ", $slug ) ) ;          
        $slug = str_replace( " ", "", $slug );    
        $slug = $first_const_str . $slug . $second_const_str;

        /* Update flag to to true */

        update_post_meta( $post->ID, 'is_slug_updated', TRUE);        
    }

    /* here we are checking if post is already published then no need to update the slug */

    if( $post->post_type == 'post' && $post->post_status == 'publish' ) {

        $slug = $post->post_name;
    }    

    return $slug;
}

add_filter( 'wp_unique_post_slug', 'custom_unique_post_slug', 10, 4 );