Q:

How do I query for a partition keys that contain a specific substring in dynamoDb? 

I have a partitionKey that is made up 2 strings for e.g. userId:UserName.  For e.g 1234:John, 4567:Mark etc.  I want to query for all the records that match the substring defined by UserName for e.g. Find all the records that contain "Mark" in the partition key.  How do I do this using DynamoDb APIs in Java? 

A:

Hopefully this is not something that you have to do frequently. 
DynamoDB does not support querying by partial hash-key.  You would have to use a table scan to iterate over all elements in the table and compare each one for matches. 
This is highly inefficient and if you find yourself depending on this type of behavior then you have to revisit your choice of hash-key and your over-all design choices.  
For the sake of completeness, the code you're looking for is along the following lines if you're using the Document API:
// dynamo returns results in chunks - you'll need this to get the next one
Map<String, AttributeValue> lastKeyEvaluated = null;

do {
   ScanRequest scanRequest = new ScanRequest()
       .withTableName("YourTableNameHere")
       .withExclusiveStartKey(lastKeyEvaluated);

   ScanResult result = client.scan(scanRequest);
   for (Map<String, AttributeValue> item : result.getItems()){
       // for each item in the result set, examine the partition key
       // to determine if it's a match
       string key = item.get("YourPartitionKeyAttributeNameHere").getS();
       if (key.startsWith("Mark"))
           System.out.println("Found an item that matches *:Mark:\n" + item);
   }
   lastKeyEvaluated = result.getLastEvaluatedKey();
} while (lastKeyEvaluated ! = null);

But before you implement something like this in your application consider choosing a different partition key strategy, or creating a secondary index for your table, or both - if you need to make this type of query often! 
As a side note, I'm curious, what benefit do you get by including both user id and user name in the partition key?   The user id would, presumably, be unique for you so why the user name?