// Find k’th character of decoded string

FindKthCharInDecodedString.js

// Find k’th character of decrypted string

// Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2″ and k=4 , so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.

// Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3″, ab is repeated 12 times. No leading 0 is present in frequency of substring.

// Examples:

// Input: "a2b2c3", k = 5
// Output: c
// Decrypted string is "aabbccc"

// Input : "ab4c2ed3", k = 9
// Output : c
// Decrypted string is "ababababccededed"

// Input: "ab4c12ed3", k = 21
// Output: e
// Decrypted string is "ababababccccccccccccededed"

///////////// Analysis 
//// in-efficient approach is
/// decode the string and get k

///// efficient approach is
/// at high level
// count the total chars just by looking at encoded string 
// assign boundary indexes to substrings
// calculate character at k within the substring


/// function to break encoded string to array of substrings
//// a substring is a string of characters between two numbers
///// Runtime O(N), where N is length of string
function findSubstrings(str) {
	var i=0;
	var subStrs = {};
	var temp_substr ="";
	var temp_substrcnt = "";
	for(i=0;i<str.length;i++) {
		//encountered a number, temp now contains the substring
		if(str[i] == '1' || str[i] == '2' || str[i] == '3'|| str[i] == '4'|| str[i] == '5'|| str[i] == '6'|| str[i] == '7'|| str[i] == '8'|| str[i] == '9') {
			//now find out the number following string, keep incrementing i till an alphabet is found or end of string is reached
			while((str[i] == '1' || str[i] == '2' || str[i] == '3'|| str[i] == '4'|| str[i] == '5'|| str[i] == '6'|| str[i] == '7'|| str[i] == '8'|| str[i] == '9')) {
				temp_substrcnt = temp_substrcnt + str[i];
				i++;
			}
			subStrs[temp_substr] = parseInt(temp_substrcnt);
			//reset temp variables
			temp_substr ="";
			temp_substrcnt="";
			i--; //point back to the first occurance of last alphabet
		}
		else {
			temp_substr = temp_substr + str[i];
		}
	}
	return subStrs;
}


//// function to read the substring dictionary and create the decoded string
////// runtime depends on the number of substrings (n) and length of each substring (m) ==> O(mn)
function decodeString(str) {
	ss = findSubstrings(str);
	ds = "";
	for(s in ss) {
		for(j=0;j<ss[s];j++) {
			ds = ds + s;
		}
	}
	return ds;
}


/// naive solution , decode the string and find kth letter in decoded string
//// runtime O(mn)+O(N) where number of substrings (n) and length of each substring (m) and N is length of string
function solution1(str,k) {
	ds = decodeString(str);
	return ds[k-1];
}

//////////////////////////////////////////////
////// validation
//////////////////////////////////////////////
console.log(solution1("a2b2c3",5));
console.log(solution1("ab4c2ed3",9));
console.log(solution1("ab4c12ed3",21));