the-strongest-string-1-1

Maga and Alex are good at string manipulation problems. Just now they have faced a problem related to string. But it is not a standard string problem. They have no idea to solve it. They need your help.

A string is called unique if all characters of string are distinct.

String s_1 is called subsequence of string s_2 if s_1 can be produced from s_2 by removing some characters of s_2.

String s_1 is stronger than s_2 if s_1 is lexicographically greater than s_2.

You are given a string. Your task is to find the strongest unique string which is subsequence of given string.

Input:

first line contains length of string.
second line contains the string.

Output:

Output the strongest unique string which is subsequence of given string.

Constraints:

1 ≤ |S| ≤ 100000   

All letters are lowercase English letters.

SAMPLE INPUT
5
abvzx

SAMPLE OUTPUT
zx

Explanation

Select all subsequence of the string and sort them in ascending order. The greatest of all is zx.

Source: hackerearth | Difficulty: EASY
Tags: Data structures

Implementation

Ad-hoc


Solutions:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# https://www.hackerearth.com/gsf-hacks/algorithm/the-strongest-string-1-1/

n = int(input())
s = input()

result = ''
start = 0
for i in range(ord('z'), ord('a') - 1, -1):
	ch = chr(i)
	for j in range(start, len(s)):
		if s[j] == ch:
			result += ch
			start = j + 1
			break
print(result)


length = input("")
str1 = input("")
str2 =[]
str3 =""
tmpList =[]
sortedList=[]
newList =[]
final =[]
j = 0
i = 0

for ch in str1:
	code = ord(ch)
	str2.append(code)
	
def find(s, ch):
	return [i for i, ltr in enumerate(s) if ltr == ch]    
	
	
sortedList = list(set(sorted(str2)))

finalList = sorted(sortedList,reverse=True)
#print finalList
highestValue = finalList[0]
#print highestValue
newList = finalList[1:]
#print newList

final.append(highestValue)
index_highest = str2.index(highestValue)
for each in newList:
	#print "each:%s and highest: %s" %(each,highestValue)
	index_each = find(str2,each)    
	#print "high_index: %s and index_each:%s" %(index_highest,index_each)

	for each1 in index_each:
		if  each1 > index_highest :
			
			final.append(each)
			#print "index_now : %s \n index_highest : %s \n  final:%s" %(each1,index_highest,final)
			index_highest =  each1
			break
		else:
			pass 
			  
			
			
for ascii in final:
	asc = chr(ascii)
	str3 = str3 + asc         
		
print(str3)



def find_strongest(s):
	alphabet = "zyxwvutsrqponmlkjihgfedcba"
	r = ""
	for c in alphabet:
		i = s.find(c)
		if i != -1:
			r = r + s[i]
			s = s[i:]
			continue
	return r

length = int(input().rstrip("\n"))
input = input().rstrip("\n")
print(find_strongest(input))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
letters = [chr(i) for i in range(123,96,-1)]
x = int(input())
s = input()
list_s = list(s)

ans = ""
for i in letters :
	if i in list_s :
		list_s = list_s[list_s.index(i) + 1 :]
		ans+=i
print(ans)