Deleting characters from a string so it stays the largest string possible

[bgdanghe]

I have this problem I've been trying to solve today... It may sound stupid but I can't get around it.

A string of characters (non-capitals only, no spaces) and a number k are input. I have to delete exactly k letters, so the string I'm left with is as large as lexicographically alphabetically possible (a is smallest, z is biggest). That is, I should delete the smallest letters starting from the front.

The problem is my program is only returning irrelevant values (for instance, "pixels" with k = 3 should return "xls", while this code is returning "px". I've commented my code saying exactly how I'm trying to do it... hope somebody can help me :)

Thanks!

  // Given a string of max 1000 characters, delete exactly k of them so the remaining letters form the biggest string lexicographically possible.

#include "stdafx.h"
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin ("data.in");
ofstream fout ("data.out");

char text[1001], lg_value;
int i, j, k, lg_place, start_place;

void input () {
	fin>>k>>text;
}

void extract () {
	start_place=0;
	while (k) {
		lg_value=0;
		lg_place=0;

		for (i=start_place; i<=start_place+k; i++) {        //search currect k span for largest value
			if (text[i]>lg_value) {
				lg_value=text[i];
				lg_place=i;
			}
		}

		for (i=start_place; i<start_place+lg_place; i++) {        //mark for deletion every letter in front of largest value; will actually be deleted at end of function
			text[i]=0;
			k--;
		}

		start_place=lg_place+1;        //position start marker after largest value; next k span starts there, with k = k - number of deleted letters

	}
	
	for (i=1; i<=strlen(text); i++)        //finally delete letters marked for deletion
		if (text[i]==0)
			for (j=i; j<=strlen(text); j++)
				text[i]=text[i+1];

}

int _tmain(int argc, _TCHAR* argv[])
{
	input();
	extract();
	fout<<text;
	system ("PAUSE");
	return 0;
}

Ignore system pause and all the main arguments... I'm using VS so those are put there automatically.

[JLBorges]

std::string makes life a lot easier.

#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>

// remove k characters from str to yield the lexicographically largest string
std::string delete_k_verbose( const std::string& str, std::size_t k )
{
    if( k == 0 ) return str ;
    else if( k >= str.size() ) return "" ;

    // search currect k span for largest value
    const auto iter = std::max_element( str.begin(), str.begin() + k+1 ) ;
    const auto pos = iter - str.begin() ;

    // rest of the string after the largest
    const std::string tail = str.substr(pos+1) ;

    // number of characters still to be removed
    auto n_left = k - pos ;

    // tail after removing n_left characters
    const std::string shortened_tail = delete_k_verbose( tail, n_left ) ;

    // the result string is: this character + shortened tail
    return *iter + shortened_tail ;
}

// ******************************************************
std::string delete_k( const std::string& str, std::size_t k ) 
{
    if( k == 0 ) return str ;
    else if( k >= str.size() ) return "" ;

    const auto iter = std::max_element( str.begin(), str.begin() + k+1 ) ;
    const auto pos = iter - str.begin() ;

    return *iter + delete_k( str.substr(pos+1), k-pos ) ;
}
// ******************************************************

std::string delete_k_bgdanghe( std::string str, std::size_t k )
{
    if( k >= str.size() ) return "" ;

    // start at the beginning
    auto begin = str.begin() ;
    while(k)
    {
        // search currect k span for largest value
        auto iter_largest = std::max_element( begin, begin + k+1 ) ;

        // mark for deletion every letter in front of largest value
        std::fill( begin, iter_largest, 0 ) ;

        k -= iter_largest - begin ; // update k

        // position start marker after largest value
        begin = iter_largest + 1 ;
    }

    // finally delete letters marked for deletion
    std::string result ;
    for( char c : str ) if(c) result += c ; // copy non-deleted letters to result

    return result ;
}

const char* delete_k_cstr( char* cstr, std::size_t k )
{ return std::strcpy( cstr, delete_k(cstr,k).c_str() ) ; }

int main()
{
    std::cout << delete_k_verbose( "pixels", 3 ) << '\n' // xls
               << delete_k( "ympixeazls", 5 ) << '\n' // yxzls
               << delete_k_bgdanghe( "xpixelsx", 4 ) << '\n' ; // xxsx

    char cstr[] = "ambcdyaa" ;
    std::cout << delete_k_cstr( cstr, 4 ) << '\n' ; // myaa
}

http://coliru.stacked-crooked.com/a/e41a2a34bc978e81

[bgdanghe]

Thanks, it's definitely easier to get the way you put it. I have to learn using string better :)