# LeetCode 880. Decoded String at Index (Medium)

LeetCode 880. Decoded String at Index: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Decoded String at Index” or “LeetCode 880.”

Leet Code 2612 Minimum Reverse Operations (Hard)

## Approach: Reverse LeetCode 880. Decoded String at Index

Leet code 880, “Decoded String at Index,” challenges us to decode a given string and find the character at a specific index.

### Steps of Approach for LeetCode 880 (Decoded String at Index)

#### 1: Calculate Total Length (Leet Code 880.)

• Iterate through the input string character by character.
• If a digit is encounter, multiply the total length by that digit.
• For non-digits, increment the total length.

#### 2: Reverse Traversal

• Start from the end of the string.
• If a digit is encounter, reduce the total length accordingly and update the target index ‘k’ to ensure it remains within bounds.
• If a non-digit character is reach, check if we’ve found the desired index ‘k’ or if the total length becomes zero. If so, return the character.

#### 3: Return Result

• If no character is found in the traversal, return an empty string.

LeetCode 2233 Maximum Product After K Increments (Medium)

Leetcode 775. Find The Global and Local Inversions (Medium)

## Code for Reverse Approach (Decoded String at Index)

### C++: Leet Code 880

``````class Solution {
public:
string decodeAtIndex(string s, int k) {
//d is deocoded string
long long d=0;
for(auto x:s){

//check the if digit occure , we will update length of string

if(isdigit(x)){
d=d*(x-'0');
}

//other wise increment by 1

else{
d++;
}
}

//we have total length build by the string and no
//reverse travesal

for(int i=s.size()-1;i>=0;i--){

//check the it char is digit

if(isdigit(s[i])){

//we will reduce the length of decoded string by digit we get

d/=(s[i]-'0');

//also we reduce the k index

k = k % d;
}
else{

//if we reached at end or found the index k

if(k==0 || k==d){
return string("")+s[i];
}
d--;
}

}

return "";
}
};``````

Leetcode 316. Remove Duplicate Letters (Medium)

### Java: Leet Code 880

``````public class Solution {
public String decodeAtIndex(String s, int k) {
long  d = 0;
for (char x : s.toCharArray()) {
if (Character.isDigit(x)) {
d = d * (x - '0');
} else {
d++;
}
}

for (int i = s.length() - 1; i >= 0; i--) {
if (Character.isDigit(s.charAt(i))) {
d = d / (s.charAt(i) - '0');
k %= d;
} else {
if (k == 0 || k == d) {
return String.valueOf(s.charAt(i));
}
d--;
}
}

return "";
}
}
``````

LeetCode 389. Find The Difference (Easy)

### Python: Decoded String at Index

``````class Solution:
def decodeAtIndex(self, s: str, k: int) -> str:
d = 0
for x in s:
if x.isdigit():
d = d * int(x)
else:
d += 1

for i in range(len(s) - 1, -1, -1):
if s[i].isdigit():
d = d // int(s[i])
k = k % d
else:
if k == 0 or k == d:
return s[i]
d -= 1

return ""
``````

Leet code 799. Champagne Tower (Medium)

### JavaScript: Decoded String at Index

``````var isNum = function(char) {
return char >= '0' && char <= '9';
}

var decodeAtIndex = function(S, K) {
var d = [isNum(S) ? 0 : 1];

for (var i = 1; i < S.length; i++) {
var char = S[i];
if (isNum(char)) {
d.push(d[i - 1] * parseInt(char));
} else {
d.push(d[i - 1] + 1);
}
}

for (var i = S.length - 1; i >= 0; i--) {
K %= d[i];
if (K === 0 && !isNum(S[i])) {
return S[i];
}
}
};
``````

Leet Code 1048. Longest String Chain (Medium)

## Result Analysis :

Leet code 206 Reverse Linked List (EAZY)

## Other approached to solve

1. Brute Force Simulation (Not Recommended): You can simulate the decoding process step by step until you reach the ‘k’ position. However, this approach is not efficient and can be very slow for large ‘k’ values.
2. Optimized Search: You can optimize the search by performing a binary search to find the character at the ‘k’ position. Use a similar length calculation as the mathematical approach to determine which part of the string to explore based on ‘k’.
3. Dynamic Programming: Precompute the length of the decoded string for a given prefix and store it in an array. Then, you can use this precomputed information to find the character at the ‘k’ position. I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.