How to remove one specific category (uncategorized) from post permalinks

Adding this kind of rewrite rule is not a problem, you have to add only this code.

/**
 * Add custom rewrite rule to handle posts with and without category prefix.
 *
 * Remember to flush rewrite rules to apply changes.
 */
function wpse_288675_add_post_handling_without_category_prefix() {

    add_rewrite_rule('([^/]+)(?:/([0-9]+))?/?$', 'index.php?name=$matches[1]&page=$matches[2]', 'top');
}

These rewrite rules are working on when I set my permalink structure to /%category%/%postname%/.

Problem is that your content will be available under two links. With %category% prefix and without. To prevent duplicate content which is bad for SEO we must redirect using 301 code all not uncaterogized post to url with category and all uncaterogized post to url without category. We can achive this using code below.

/**
 * Check if displayed post have category and which category to maybe redirect user
 * with 301 code to prevent duplicate content.
 */
function wpse_288675_maybe_redirect( $query ) {

    // Define uncaterogized category id for convenience
    if( ! defined( 'UNCATEROGIZED_CATEGORY_ID' ) ) {
        define( 'UNCATEROGIZED_CATEGORY_ID', 1 );
    }

    // Do not parse request on some conditions
    if( !is_admin() && $query->is_main_query() && $query->is_single() ) { 

        // Get post name and category from url
        $slug          = $query->get('name');
        $category_name = $query->get('category_name');

        $query = new WP_Query(array(
            'post_type' => 'post',
            'name' => $slug,
        ));

        if( $query->have_posts() ) {

            // Get current post
            $posts = $query->get_posts();
            $post = current($posts);

            // Get post current first category
            $categories = get_the_category( $post->ID );
            $category   = current($categories);

            // If there is no category in url redirect
            // all not uncaterogized post to url with category
            if( !$category_name && $category->term_id !== UNCATEROGIZED_CATEGORY_ID ) { 
                wp_safe_redirect( get_permalink( $post->ID ), 301 );
                exit;
            }

            // If there is category in url redirect
            // all uncaterogized post to url without category
            if($category_name && $category->term_id === UNCATEROGIZED_CATEGORY_ID ) { 

                $url_format="%s/%s/";
                $url = sprintf($url_format, get_bloginfo('url'), $slug);

                wp_safe_redirect( $url, 301 );
                exit;
            }
        }
    }

    return $query;
}

add_filter( 'pre_get_posts', 'wpse_288675_maybe_redirect' );

I will describe how this code is working on example. I have two posts:

• Test 1 with category Uncaterogized
• Test 2 with category Category 1

When I get to /uncaterogized/test-1/ I’m redirecting to /test-1/.
When I get to /category-1/test-2 I’m not redirected.